三段回文（困难版）

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一个由正整数组成的序列 $a$。

如果一个序列至多包含两种不同的元素（记为 $x$ 和 $y$，允许 $x=y$），并且可以写成

$$[\underbrace{x,x,\ldots,x}_{p},\underbrace{y,y,\ldots,y}_{q},\underbrace{x,x,\ldots,x}_{p}],$$

其中 $p,q$ 均为非负整数，那么称它为“三段回文”。例如，空序列、$[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$ 能够由序列 $s$ 删除若干个（也可以不删除）元素且不改变其余元素的相对顺序得到，那么称 $t$ 是 $s$ 的子序列。

你需要处理 $t$ 组相互独立的测试数据。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$），表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 200$）。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示最长三段回文子序列的长度。

样例输入 1

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

样例输出 1

7
2
4
1
1
3

数据范围

对于所有测试数据，$1\le t\le 10^4$，$1\le a_i\le 200$，$1\le n\le 2\times 10^5$，且单个输入文件中所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

子任务编号	分值	特殊限制
1	20	每组测试数据均满足 $n\le 18$
2	40	每组测试数据均满足 $n\le 2500$
3		无特殊限制