1935B.md (3565B)
1 Source: https://codeforces.com/problemset/problem/1935/B 2 3 B. Informatics in MAC 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 In the Master's Assistance Center, Nyam-Nyam was given a homework assignment in informatics. 22 23 There is an array $a$ of length $n$, and you want to divide it into $k \gt 1$ subsegments$^{\dagger}$ in such a way that the $\operatorname{MEX} ^{\ddagger}$ on each subsegment is equal to the same integer. 24 25 Help Nyam-Nyam find any suitable division, or determine that it does not exist. 26 27 $^{\dagger}$A division of an array into $k$ subsegments is defined as $k$ pairs of integers $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$ such that $l_i \le r_i$ and for each $1 \le j \le k - 1$, $l_{j + 1} = r_j + 1$, and also $l_1 = 1$ and $r_k = n$. These pairs represent the subsegments themselves. 28 29 $^{\ddagger}\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array. 30 31 For example: 32 33 * $\operatorname{MEX}$ of the array $[2, 2, 1]$ is $0$, because $0$ does not belong to the array. 34 * $\operatorname{MEX}$ of the array $[3, 1, 0, 1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not. 35 * $\operatorname{MEX}$ of the array $[0, 3, 1, 2]$ is $4$, because $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not. 36 37 Input 38 39 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 40 41 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the array $a$. 42 43 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt n$) — the elements of the array $a$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 46 47 Output 48 49 For each test case, output a single integer $-1$ if a suitable division does not exist. 50 51 Otherwise, on the first line, output an integer $k$ ($2 \le k \le n$) — the number of subsegments in the division. 52 53 Then output $k$ lines — the division into subsegments. The $i$-th line should contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the $i$-th subsegment. 54 55 The following conditions must be satisfied: 56 57 * For all $1 \le j \le k - 1$, $l_{j + 1} = r_j + 1$; 58 * $l_1 = 1$, $r_k = n$. 59 60 If there are multiple possible solutions, output any of them. 61 62 Example 63 64 Input 65 66 ``` 67 5 68 69 2 70 71 0 0 72 73 5 74 75 0 1 2 3 4 76 77 8 78 79 0 1 7 1 0 1 0 3 80 81 3 82 83 2 2 2 84 85 4 86 87 0 1 2 0 88 ``` 89 90 Output 91 92 ``` 93 2 94 1 1 95 2 2 96 -1 97 3 98 1 3 99 4 5 100 6 8 101 3 102 1 1 103 2 2 104 3 3 105 -1 106 ``` 107 108 Note 109 110 In the first test case, the array $a$ can be divided into $2$ subsegments with boundaries $[1, 1]$ and $[2, 2]$: 111 112 * $\operatorname{MEX}$ of the first subsegment $[0]$ is $1$, as $0$ belongs to the subsegment, but $1$ does not. 113 * $\operatorname{MEX}$ of the second subsegment $[0]$ is $1$, as $0$ belongs to the subsegment, but $1$ does not. 114 115 In the second test case, it can be proven that the required division does not exist. 116 117 In the third test case, the array $a$ can be divided into $3$ subsegments with boundaries $[1, 3]$, $[4, 5]$, $[6, 8]$: 118 119 * $\operatorname{MEX}$ of the first subsegment $[0, 1, 7]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not. 120 * $\operatorname{MEX}$ of the second subsegment $[1, 0]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not. 121 * $\operatorname{MEX}$ of the third subsegment $[1, 0, 3]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not.