B. Информатика в ЦПМ
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Центре Помощи Магистрам, Ням-Няму задали домашнее задание по информатике.

Есть массив $$$a$$$ длины $$$n$$$, вы хотите разбить его на $$$k > 1$$$ подотрезков$$$^{\dagger}$$$ таким образом, чтобы $$$\operatorname{MEX} ^{\ddagger}$$$ на каждом подотрезке был равен одному и тому же числу.

Помогите Ням-Няму найти любое подходящее разбиение, или же определите, что его не существует.

$$$^{\dagger}$$$Разбиением массива на $$$k$$$ подотрезков называется $$$k$$$ пар целых чисел $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ таких, что $$$l_i \le r_i$$$ и для каждого $$$1 \le j \le k - 1$$$ верно $$$l_{j + 1} = r_j + 1$$$, а также $$$l_1 = 1$$$ и $$$r_k = n$$$. Эти пары представляют сами подотрезки.

$$$^{\ddagger}\operatorname{MEX}$$$ массива — это наименьшее целое неотрицательное число, которое не принадлежит массиву.

Например:

  • $$$\operatorname{MEX}$$$ массива $$$[2, 2, 1]$$$ равен $$$0$$$, так как $$$0$$$ не принадлежит массиву.
  • $$$\operatorname{MEX}$$$ массива $$$[3, 1, 0, 1]$$$ равен $$$2$$$, так как $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ нет.
  • $$$\operatorname{MEX}$$$ массива $$$[0, 3, 1, 2]$$$ равен $$$4$$$, так как $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ нет.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$-1$$$, если подходящего разбиения не существует.

Иначе, в первой строке выведите целое число $$$k$$$ ($$$2 \le k \le n$$$) — количество подотрезков в разбиении.

Затем выведите $$$k$$$ строк — разбиение на подотрезки. $$$i$$$-я строка должна содержать два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы $$$i$$$-го подотрезка.

При этом должны выполняться условия:

  • Для всех $$$1 \le j \le k - 1$$$ выполнено $$$l_{j + 1} = r_j + 1$$$;
  • $$$l_1 = 1$$$, $$$r_k = n$$$.

Если существует несколько возможных решений, выведите любое из них.

Пример
Входные данные
5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
2 2 2
4
0 1 2 0
Выходные данные
2
1 1
2 2
-1
3
1 3
4 5
6 8
3
1 1
2 2
3 3
-1
Примечание

В первом наборе входных данных можно разбить массив $$$a$$$ на $$$2$$$ подотрезка с границами $$$[1, 1]$$$ и $$$[2, 2]$$$:

  • $$$\operatorname{MEX}$$$ первого подотрезка $$$[0]$$$ равен $$$1$$$, так как $$$0$$$ принадлежит подотрезку, а $$$1$$$ нет.
  • $$$\operatorname{MEX}$$$ второго подотрезка $$$[0]$$$ равен $$$1$$$, так как $$$0$$$ принадлежит подотрезку, а $$$1$$$ нет.

Во втором наборе входных данных можно доказать, что требуемого разбиения не существует.

В третьем наборе входных данных, можно разбить массив $$$a$$$ на $$$3$$$ подотрезка с границами $$$[1, 3]$$$, $$$[4, 5]$$$, $$$[6, 8]$$$:

  • $$$\operatorname{MEX}$$$ первого подотрезка $$$[0, 1, 7]$$$ равен $$$2$$$, так как $$$0$$$ и $$$1$$$ принадлежит подотрезку, а $$$2$$$ нет.
  • $$$\operatorname{MEX}$$$ второго подотрезка $$$[1, 0]$$$ равен $$$2$$$, так как $$$0$$$ и $$$1$$$ принадлежит подотрезку, а $$$2$$$ нет.
  • $$$\operatorname{MEX}$$$ третьего подотрезка $$$[1, 0, 3]$$$ равен $$$2$$$, так как $$$0$$$ и $$$1$$$ принадлежит подотрезку, а $$$2$$$ нет.