← 返回题目列表

Codeforces · 1842/C

C. 丹增和球

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

Tenzing 有 $$$n$$$ 球排列成一条线。从左边算起第 $$$i$$$ 个球的颜色是 $$$a_i$$$。

Tenzing 可以执行以下操作任意多次:

- 选择 $$$i$$$ 和 $$$j$$$ 使得 $$$1\leq i < j \leq |a|$$$ 和 $$$a_i=a_j$$$,
- 从数组中删除 $$$a_i,a_{i+1},\ldots,a_j$$$ (并将 $$$a_j$$$ 右侧所有元素的索引减少 $$$j-i+1$$$)。

Tenzing 想知道他可以移除的最大球数。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — 球的数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq n$$$) — 球的颜色。

保证所有测试用例的$$$n$$$之和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出 Tenzing 可以移除的最大球数。

示例

输入 #1

2
5
1 2 2 3 3
4
1 2 1 2

输出 #1

4
3

注意

在第一个示例中,Tenzing 将在第一个操作中选择 $$$i=2$$$ 和 $$$j=3$$$,以便 $$$a=[1,3,3]$$$。那么Tenzing将在第二次操作中再次选择$$$i=2$$$和$$$j=3$$$,使得$$$a=[1]$$$。因此,Tenzing 总共可以移除 $$$4$$$ 个球。

在第二个示例中,Tenzing 将在第一个也是唯一一个操作中选择 $$$i=1$$$ 和 $$$j=3$$$,以便 $$$a=[2]$$$。因此,Tenzing 总共可以移除 $$$3$$$ 个球。