Codeforces Round 932 (Div. 2) |
---|
Finished |
In the Master's Assistance Center, Nyam-Nyam was given a homework assignment in informatics.
There is an array $$$a$$$ of length $$$n$$$, and you want to divide it into $$$k > 1$$$ subsegments$$$^{\dagger}$$$ in such a way that the $$$\operatorname{MEX} ^{\ddagger}$$$ on each subsegment is equal to the same integer.
Help Nyam-Nyam find any suitable division, or determine that it does not exist.
$$$^{\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.
$$$^{\ddagger}\operatorname{MEX}$$$ of an array is the smallest non-negative integer that does not belong to the array.
For example:
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.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$) — the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output a single integer $$$-1$$$ if a suitable division does not exist.
Otherwise, on the first line, output an integer $$$k$$$ ($$$2 \le k \le n$$$) — the number of subsegments in the division.
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.
The following conditions must be satisfied:
If there are multiple possible solutions, output any of them.
520 050 1 2 3 480 1 7 1 0 1 0 332 2 240 1 2 0
2 1 1 2 2 -1 3 1 3 4 5 6 8 3 1 1 2 2 3 3 -1
In the first test case, the array $$$a$$$ can be divided into $$$2$$$ subsegments with boundaries $$$[1, 1]$$$ and $$$[2, 2]$$$:
In the second test case, it can be proven that the required division does not exist.
In the third test case, the array $$$a$$$ can be divided into $$$3$$$ subsegments with boundaries $$$[1, 3]$$$, $$$[4, 5]$$$, $$$[6, 8]$$$:
Name |
---|