B. Informatics in MAC
constructive algorithms
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: \(\operatorname{MEX}\) of the array \([2, 2, 1]\) is \(0\), because \(0\) does not belong to the array. \(\operatorname{MEX}\) of the array \([3, 1, 0, 1]\) is \(2\), because \(0\) and \(1\) belong to the array, but \(2\) does not. \(\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.
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: For all \(1 \le j \le k - 1\), \(l_{j + 1} = r_j + 1\); \(l_1 = 1\), \(r_k = n\).If there are multiple possible solutions, output any of them.
In the first test case, the array \(a\) can be divided into \(2\) subsegments with boundaries \([1, 1]\) and \([2, 2]\): \(\operatorname{MEX}\) of the first subsegment \([0]\) is \(1\), as \(0\) belongs to the subsegment, but \(1\) does not. \(\operatorname{MEX}\) of the second subsegment \([0]\) is \(1\), as \(0\) belongs to the subsegment, but \(1\) does not. 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]\): \(\operatorname{MEX}\) of the first subsegment \([0, 1, 7]\) is \(2\), as \(0\) and \(1\) belong to the subsegment, but \(2\) does not. \(\operatorname{MEX}\) of the second subsegment \([1, 0]\) is \(2\), as \(0\) and \(1\) belong to the subsegment, but \(2\) does not. \(\operatorname{MEX}\) of the third subsegment \([1, 0, 3]\) is \(2\), as \(0\) and \(1\) belong to the subsegment, but \(2\) does not.