Последовательность из \(m\) целых чисел называется перестановкой, если она содержит все целые числа от \(1\) до \(m\) ровно один раз. Число \(m\) называется длиной перестановки.
У Dreamoon есть две перестановки \(p_1\) и \(p_2\) имеющих ненулевые длины \(l_1\) и \(l_2\).
Затем, Dreamoon конкатенирует эти две перестановки в последовательность \(a\) длины \(l_1 + l_2\). Первые \(l_1\) элементов \(a\) это перестановка \(p_1\) а следующие \(l_2\) элементов \(a\) это перестановка \(p_2\).
Вам дана последовательность \(a\), вам нужно найти восстановить перестановки \(p_1\) и \(p_2\). Если есть несколько возможных способов, вам нужно найти все. (Обратите внимание, что также возможно, что способов не будет.)
Выходные данные
Для каждого набора входных данных, в первой строке требуется вывести число \(k\): количество способов разбить \(a\) на перестановки \(p_1\) и \(p_2\).
Каждая из следующих \(k\) строк должна содержать два целых числа \(l_1\) и \(l_2\) (\(1 \leq l_1, l_2 \leq n, l_1 + l_2 = n\)), обозначающих, что \(a\) можно разбить на две перестановки длин \(l_1\) и \(l_2\) (\(p_1\) это первые \(l_1\) элементов \(a\), а \(p_2\) это последние \(l_2\) элементов \(a\)). Вы можете выводить решения в любом порядке.
Примечание
В первом примере, есть два возможных способа разбить \(a\) на перестановки: \(\{1\} + \{4, 3, 2, 1\}\) and \(\{1,4,3,2\} + \{1\}\).
Во втором примере, есть только один способ разбить \(a\) на перестановки: \(\{2,4,1,3\} + \{2,1\}\).
В третьем примере, нет ни одного искомого разбиения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
1 4 3 2 1
6
2 4 1 3 2 1
4
2 1 1 3
4
1 3 3 1
12
2 1 3 4 5 6 7 8 9 1 10 2
3
1 1 1
|
2
1 4
4 1
1
4 2
0
0
1
2 10
0
|