Единственное отличие между простой и сложной версиями — ограничения.
Вам дана последовательность \(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]\).