CF1842C.Tenzing and Balls

Enjoy erasing Tenzing, identified as Accepted!

Tenzing has $n$ balls arranged in a line. The color of the $i$-th ball from the left is $a_i$.

Tenzing can do the following operation any number of times:

• select $i$ and $j$ such that $1\leq i \lt j \leq |a|$ and $a_i=a_j$,
• remove $a_i,a_{i+1},\ldots,a_j$ from the array (and decrease the indices of all elements to the right of $a_j$ by $j-i+1$).

Tenzing wants to know the maximum number of balls he can remove.

享受擦除腾津，状态为“已通过”！

腾津有 $n$ 个球排成一行。从左往右数第 $i$ 个球的颜色为 $a_i$。

腾津可以执行以下操作任意多次：

• 选择满足 $1\leq i \lt j \leq |a|$ 且 $a_i=a_j$ 的下标 $i$ 和 $j$；
• 将子数组 $a_i,a_{i+1},\ldots,a_j$ 从数组中移除（并将所有位于 $a_j$ 右侧的元素下标减去 $j-i+1$）。

腾津想知道他最多能移除多少个球。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) — the number of test cases. The description of test cases follows.

The first line contains a single integer $n$ ($1\leq n\leq 2\cdot 10^5$) — the number of balls.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq n$) — the color of the balls.

It is guaranteed that sum of $n$ of all test cases will not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $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$。

For each test case, output the maximum number of balls Tenzing can remove.

对于每个测试用例，输出丹增能够移除的球的最大数量。

In the first example, Tenzing will choose $i=2$ and $j=3$ in the first operation so that $a=[1,3,3]$. Then Tenzing will choose $i=2$ and $j=3$ again in the second operation so that $a=[1]$. So Tenzing can remove $4$ balls in total.

In the second example, Tenzing will choose $i=1$ and $j=3$ in the first and only operation so that $a=[2]$. So Tenzing can remove $3$ balls in total.

在第一个例子中，丹增在第一次操作中选择 $i=2$ 和 $j=3$，使得 $a=[1,3,3]$；然后在第二次操作中再次选择 $i=2$ 和 $j=3$，使得 $a=[1]$。因此，丹增总共可以移除 $4$ 个球。

在第二个例子中，丹增在唯一的一次操作中选择 $i=1$ 和 $j=3$，使得 $a=[2]$。因此，丹增总共可以移除 $3$ 个球。