E2. Палиндром из трех блоков (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дана последовательность $$$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]$$$ and $$$[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]$$$.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину $$$a$$$. Вторая строка набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 200$$$), где $$$a_i$$$ — это $$$i$$$-й элемент в $$$a$$$. Заметьте, что максимальное значение $$$a_i$$$ может быть до $$$200$$$.

Гарантируется, что сумма чисел $$$n$$$ по всем наборам тестовых данных не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ на него — максимально возможную длину некоторой подпоследовательности $$$a$$$, которая является палиндромом из трех блоков.

Пример
Входные данные
6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1
Выходные данные
7
2
4
1
1
3