← 返回题目列表

Codeforces · 1488/E

E. 回文双打

中文机器翻译题面 查看原题

子序列是可以通过从另一个序列中删除一些元素而不改变剩余元素的顺序而获得的序列。

回文序列是等于其自身反转的序列。

给你一个 $$$n$$$ 整数序列 $$$a_1, a_2, \dots, a_n$$$。任何整数值在 $$$a$$$ 中出现的次数不得超过两次。

序列 $$$a$$$ 的最长回文子序列的长度是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 250\,000$$$) — 序列中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。

任何整数值在 $$$a$$$ 中出现的次数不得超过两次。所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个测试用例,打印一个整数 - 序列 $$$a$$$ 的最长回文子序列的长度。

示例

输入 #1

5
6
2 1 3 1 5 2
6
1 3 3 4 4 1
1
1
2
1 1
7
4 4 2 5 7 2 3

输出 #1

5
4
1
2
3

注意

以下是示例测试用例的最长回文子序列:

- 2 1 3 1 5 2
- 1 3 3 4 4 1 或 1 3 3 4 4 1
- 1
- 1 1
- 4 4 2 5 7 2 3 或 4 4 2 5 7 2 3