В Центре Помощи Магистрам, Ням-Няму задали домашнее задание по информатике.
Есть массив \(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\) нет.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(-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\).
Если существует несколько возможных решений, выведите любое из них.
Примечание
В первом наборе входных данных можно разбить массив \(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\) нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|