暂无测试数据。

F. Tenzing and Balls

Enjoy erasing Tenzing, identified as Accepted!

时间限制：1 seconds

空间限制：256 megabytes

原题链接：https://codeforces.com/gym/451807/problem/F

题目描述

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能够移除的最大球数。

样例

输入样例

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

输出样例

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\)个球。