1842C.md (1698B)
1 Source: https://codeforces.com/problemset/problem/1842/C 2 3 C. Tenzing and Balls 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Enjoy erasing Tenzing, identified as Accepted! 22 23 Tenzing has $n$ balls arranged in a line. The color of the $i$-th ball from the left is $a_i$. 24 25 Tenzing can do the following operation any number of times: 26 27 * select $i$ and $j$ such that $1\leq i \lt j \leq |a|$ and $a_i=a_j$, 28 * 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$). 29 30 Tenzing wants to know the maximum number of balls he can remove. 31 32 Input 33 34 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. 35 36 The first line contains a single integer $n$ ($1\leq n\leq 2\cdot 10^5$) — the number of balls. 37 38 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq n$) — the color of the balls. 39 40 It is guaranteed that sum of $n$ of all test cases will not exceed $2\cdot 10^5$. 41 42 Output 43 44 For each test case, output the maximum number of balls Tenzing can remove. 45 46 Example 47 48 Input 49 50 ``` 51 2 52 53 5 54 55 1 2 2 3 3 56 57 4 58 59 1 2 1 2 60 ``` 61 62 Output 63 64 ``` 65 4 66 3 67 ``` 68 69 Note 70 71 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. 72 73 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.