← 返回题目列表

Codeforces · 1699/D

D. 几乎三重删除

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

给定一个整数 $$$n$$$ 和一个数组 $$$a_1,a_2,\ldots,a_n$$$。

在一次操作中,您可以为 $$$a_i \neq a_{i+1}$$$ 选择索引 $$$i$$$ ($$$1 \le i \lt n$$$) 并从数组中删除 $$$a_i$$$ 和 $$$a_{i+1}$$$。删除 $$$a_i$$$ 和 $$$a_{i+1}$$$ 后,数组的其余部分被连接起来。

例如,如果 $$$a=[1,4,3,3,6,2]$$$,则执行 $$$i=2$$$ 运算后,结果数组将为 $$$[1,3,6,2]$$$。

通过执行几个(也许没有)上述操作,从 $$$a$$$ 获得的相等元素数组的最大可能长度是多少?

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。以下行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10\,000$$$。

输出

对于每个测试用例,打印一个整数,即通过执行一系列操作从 $$$a$$$ 获得的相等元素数组的最大可能长度。

示例

输入 #1

5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3

输出 #1

3
1
0
4
2

注意

对于第一个测试用例,最佳操作顺序为:$$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$。

对于第二个测试用例,数组中的所有元素都已经相等。

对于第三个测试用例,唯一可能的操作顺序是:$$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$。注意,根据声明,每一步删除的元素必须不同。

对于第四个测试用例,最佳操作顺序是:$$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$。

对于第五个测试用例,两个相等元素的一个可能可达数组是 $$$[4,4]$$$。