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$$$ 个球。