2117C.md (2482B)
1 Source: https://codeforces.com/problemset/problem/2117/C 2 3 C. Cool Partition 4 5 time limit per test 6 7 2 seconds 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 Yousef has an array $a$ of size $n$. He wants to partition the array into one or more contiguous segments such that each element $a_i$ belongs to exactly one segment. 22 23 A partition is called cool if, for every segment $b_j$, all elements in $b_j$ also appear in $b_{j + 1}$ (if it exists). That is, every element in a segment must also be present in the segment following it. 24 25 For example, if $a = [1, 2, 2, 3, 1, 5]$, a cool partition Yousef can make is $b_1 = [1, 2]$, $b_2 = [2, 3, 1, 5]$. This is a cool partition because every element in $b_1$ (which are $1$ and $2$) also appears in $b_2$. In contrast, $b_1 = [1, 2, 2]$, $b_2 = [3, 1, 5]$ is not a cool partition, since $2$ appears in $b_1$ but not in $b_2$. 26 27 Note that after partitioning the array, you do not change the order of the segments. Also, note that if an element appears several times in some segment $b_j$, it only needs to appear at least once in $b_{j + 1}$. 28 29 Your task is to help Yousef by finding the maximum number of segments that make a cool partition. 30 31 Input 32 33 The first line of the input contains integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array. 38 39 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, print one integer — the maximum number of segments that make a cool partition. 44 45 Example 46 47 Input 48 49 ``` 50 8 51 52 6 53 54 1 2 2 3 1 5 55 56 8 57 58 1 2 1 3 2 1 3 2 59 60 5 61 62 5 4 3 2 1 63 64 10 65 66 5 8 7 5 8 5 7 8 10 9 67 68 3 69 70 1 2 2 71 72 9 73 74 3 3 1 4 3 2 4 1 2 75 76 6 77 78 4 5 4 5 6 4 79 80 8 81 82 1 2 1 2 1 2 1 2 83 ``` 84 85 Output 86 87 ``` 88 2 89 3 90 1 91 3 92 1 93 3 94 3 95 4 96 ``` 97 98 Note 99 100 The first test case is explained in the statement. We can partition it into $b_1 = [1, 2]$, $b_2 = [2, 3, 1, 5]$. It can be shown there is no other partition with more segments. 101 102 In the second test case, we can partition the array into $b_1 = [1, 2]$, $b_2 = [1, 3, 2]$, $b_3 = [1, 3, 2]$. The maximum number of segments is $3$. 103 104 In the third test case, the only partition we can make is $b_1 = [5, 4, 3, 2, 1]$. Any other partition will not satisfy the condition. Therefore, the answer is $1$.