B. Dreamoon любит перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность из $$$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$$$. Если есть несколько возможных способов, вам нужно найти все. (Обратите внимание, что также возможно, что способов не будет.)

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$): количество наборов входных данных.

Каждый набор входных данных описывается двумя строками.

В первой строке записано целое число $$$n$$$ ($$$2 \leq n \leq 200\,000$$$): длина $$$a$$$.

Во второй строке записано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n-1$$$).

Сумма по всем $$$n$$$ не превосходит $$$200\,000$$$.

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

Для каждого набора входных данных, в первой строке требуется вывести число $$$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$$$). Вы можете выводить решения в любом порядке.

Пример
Входные данные
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
Примечание

В первом примере, есть два возможных способа разбить $$$a$$$ на перестановки: $$$\{1\} + \{4, 3, 2, 1\}$$$ and $$$\{1,4,3,2\} + \{1\}$$$.

Во втором примере, есть только один способ разбить $$$a$$$ на перестановки: $$$\{2,4,1,3\} + \{2,1\}$$$.

В третьем примере, нет ни одного искомого разбиения.