2227D.md (2495B)
1 Source: https://codeforces.com/problemset/problem/2227/D 2 3 D. Palindromex 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 given you an array $a$ of $2n$ integers. Every integer $x \in [0, n - 1]$ appears exactly twice in the array. 22 23 Your task is to find a subarray $a_l, a_{l + 1}, \dots, a_r$ that is a palindrome$^{\text{∗}}$ such that its $\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$$^{\text{†}}$ is maximized. Output this maximum possible value. 24 25 $^{\text{∗}}$A palindrome is a string that reads the same backward as forward, for example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not. 26 27 $^{\text{†}}$The $\operatorname{mex}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example: 28 29 * The $\operatorname{mex}$ of $[2,2,1]$ is $0$, because $0$ does not belong to the array. 30 * The $\operatorname{mex}$ of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not. 31 * The $\operatorname{mex}$ of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not. 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$). 38 39 The second line of each test case contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($0 \le a_i \le n-1$). It is guaranteed that every integer in the range $[0, n-1]$ appears exactly twice. 40 41 It is guaranteed that the sum of $2n$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, output a single integer — the maximum $\operatorname{mex}$ of any palindromic subarray. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 54 4 55 56 1 2 0 3 3 0 2 1 57 58 2 59 60 0 1 0 1 61 62 2 63 64 1 1 0 0 65 66 3 67 68 2 0 2 1 1 0 69 70 4 71 72 0 1 3 0 3 1 2 2 73 74 3 75 76 0 1 2 1 0 2 77 ``` 78 79 Output 80 81 ``` 82 4 83 84 2 85 86 1 87 88 1 89 90 2 91 92 3 93 ``` 94 95 Note 96 97 In the first test case, the only optimal subarray to choose is $a[1, 8] = [1, 2, 0, 3, 3, 0, 2, 1]$, which is palindromic and has a $\operatorname{mex}$ of $4$. 98 99 In the second test case, one of the optimal subarrays to choose is $a[2, 4] = [1, 0, 1]$, which is palindromic and has a $\operatorname{mex}$ of $2$. 100 101 In the third test case, we can choose $a[3, 3] = [0]$, which is palindromic and has a $\operatorname{mex}$ of $1$. No other palindromic subarray has a $\operatorname{mex}$ greater than $1$.