310492: CF1842C. Tenzing and Balls
Description
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 < 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.
InputEach 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$.
OutputFor each test case, output the maximum number of balls Tenzing can remove.
ExampleInput2 5 1 2 2 3 3 4 1 2 1 2Output
4 3Note
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.
Input
题意翻译
有一个大小为 $n$ 的数组 $a$。你可以进行下列操作任意多次: 选择 $i$ 和 $j$,使$1\leq i \lt j \leq |a|$ 并且$a_i=a_j$, 从数组中删除 $a_i,a_{i+1},…,a_{j}$ (并将 $a_j$ 右边的所有元素的索引减少 $j−i+1$)。 求出能删除数的最大数量。 注:$|a|$ 表示 $a$ 数组的大小。Output
Tenzing有一排共n个球,从左到右第i个球的颜色是a_i。Tenzing可以进行以下操作任意次:
- 选择i和j(1≤i
Tenzing想知道他最多能移除多少个球。
**输入数据格式:**
每个测试包含多个测试案例。第一行输入包含一个整数t(1≤t≤10^3)——测试案例的数量。接下来是测试案例的描述。
每个案例的第一行包含一个整数n(1≤n≤2×10^5)——球的数量。
第二行包含n个整数a_1, a_2, …, a_n(1≤a_i≤n)——球的颜色的序列。
保证所有测试案例的n之和不超过2×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],然后再选择i=2和j=3,得到a=[1]。所以Tenzing总共可以移除4个球。
在第二个例子中,Tenzing选择i=1和j=3进行操作,得到a=[2]。所以Tenzing总共可以移除3个球。**题目大意:** Tenzing有一排共n个球,从左到右第i个球的颜色是a_i。Tenzing可以进行以下操作任意次: - 选择i和j(1≤i