Единственное отличие между простой и сложной версиями — ограничения.

Вам дана последовательность $$$a$$$, состоящая из $$$n$$$ положительных чисел.

Определим палиндром из трех блоков как последовательность, которая состоит из не более, чем двух различных элементов (назовем эти элементы $$$a$$$ и $$$b$$$, $$$a$$$ может быть равно $$$b$$$) и выглядит следующим образом $$$[\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}]$$$. Здесь $$$x, y$$$ — числа, большие или равные $$$0$$$. Например, последовательности $$$[]$$$, $$$[2]$$$, $$$[1, 1]$$$, $$$[1, 2, 1]$$$, $$$[1, 2, 2, 1]$$$ и $$$[1, 1, 2, 1, 1]$$$ — палиндромы из трех блоков, но $$$[1, 2, 3, 2, 1]$$$, $$$[1, 2, 1, 2, 1]$$$ и $$$[1, 2]$$$ — нет.

Ваша задача — выбрать максимальную по длине подпоследовательность $$$a$$$, которая является палиндромом из трех блоков.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

Напомним, что последовательность $$$t$$$ является подпоследовательностью последовательности $$$s$$$, если $$$t$$$ может быть получена из $$$s$$$ после удаления нуля или более элементов без изменения порядка оставшихся элементов. Например, если $$$s=[1, 2, 1, 3, 1, 2, 1]$$$, то возможные подпоследовательности: $$$[1, 1, 1, 1]$$$, $$$[3]$$$ и $$$[1, 2, 1, 3, 1, 2, 1]$$$, но не $$$[3, 2, 3]$$$ and $$$[1, 1, 1, 1, 2]$$$.