H. Обьединение множеств
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a_1, a_2, \dots, a_n$$$ чисел от $$$1$$$ до $$$n$$$. Также у вас есть $$$n$$$ множеств $$$S_1,S_2,\dots, S_n$$$, где $$$S_i=\{a_i\}$$$. Наконец, у вас есть переменная $$$cnt$$$, представляющая текущее количество наборов. Первоначально $$$cnt = n$$$.

Мы определяем два вида функций на множествах:

$$$f(S)=\min\limits_{u\in S} u$$$;

$$$g(S)=\max\limits_{u\in S} u$$$.

Вы можете получить новое множество, объединив два множества $$$A$$$ и $$$B$$$, если они удовлетворяют $$$g(A)<f(B)$$$ (обратите внимание, что старые множества не исчезают).

Формально, вы можете выполнить следующую последовательность операций:

  • $$$cnt\gets cnt+1$$$;

  • $$$S_{cnt}=S_u\cup S_v$$$, вы можете выбрать любые $$$u$$$ и $$$v$$$ для которых $$$1\le u, v < cnt$$$ и для которых выполняется $$$g(S_u)<f(S_v)$$$.

Вам необходимо получить некоторые конкретные множества.

Существуют $$$q$$$ требований, каждое из которых задается двумя целыми числами $$$l_i$$$, $$$r_i$$$, что означает, что должно существовать множество $$$S_{k_i}$$$ ($$$k_i$$$  — это индекс набора, его нужно будет задать) равное $$$\{a_u\mid l_i\leq u\leq r_i\}$$$, то есть множество, состоящее из всех $$$a_i$$$ с индексами между $$$l_i$$$ и $$$r_i$$$.

В конце должно выполняться $$$cnt\leq 2.2\times 10^6$$$. Заметьте, что вы не должны минимизировать $$$cnt$$$. Гарантируется, что решение при данных ограничениях существует.

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

Первая строка содержит два целых числа $$$n,q$$$ $$$(1\leq n \leq 2^{12},1 \leq q \leq 2^{16})$$$  — длину перестановки и количество необходимых множеств соответственно.

Следующая строка состоит из $$$n$$$ целых чисел $$$a_1,a_2,\cdots, a_n$$$ ($$$1\leq a_i\leq n$$$, $$$a_i$$$ попарно различны)  — данная перестановка.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_i,r_i$$$ $$$(1\leq l_i\leq r_i\leq n)$$$, описывающих требование к $$$i$$$-у множеству.

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

Гарантируется, что решение при данных ограничениях существует.

Первая строка должна содержать одно целое число $$$cnt_E$$$ $$$(n\leq cnt_E\leq 2.2\times 10^6)$$$, равное количеству множеств после всех операций.

Должны следовать $$$cnt_E-n$$$ строк, каждая строка должна содержать два целых числа $$$u$$$, $$$v$$$ ($$$1\leq u, v\leq cnt'$$$, где $$$cnt'$$$  — это значение $$$cnt$$$ до этой операции) Это означает, что вы выбираете $$$S_u$$$, $$$S_v$$$ и выполняете операцию слияния. В операции должно быть выполнено $$$g(S_u)<f(S_v)$$$.

Последняя строка должна содержать $$$q$$$ целых чисел $$$k_1,k_2,\cdots,k_q$$$ $$$(1\leq k_i\leq cnt_E)$$$, представляющих, что набор $$$S_{k_i}$$$ является $$$i$$$-м необходимым набором.

Пожалуйста, обратите внимание на большое количество вывода.

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

В первом примере:

Изначально у нас есть $$$S_1=\{1\},S_2=\{3\},S_3=\{2\}$$$.

В первой операции, поскольку $$$g(S_3)=2<f(S_2)=3$$$, мы можем объединить $$$S_3,S_2$$$ в $$$S_4=\{2,3\}$$$.

Во второй операции, поскольку $$$g(S_1)=1<f(S_3)=2$$$, мы можем объединить $$$S_1,S_3$$$ в $$$S_5=\{1,2\}$$$.

В третьей операции, поскольку $$$g(S_5)=2<f(S_2)=3$$$, мы можем объединить $$$S_5,S_2$$$ в $$$S_6=\{1,2,3\}$$$.

Для первого требования $$$S_4=\{2,3\}=\{a_2,a_3\}$$$ удовлетворяет ему, поэтому $$$k_1=4$$$.

Для второго требования $$$S_6=\{1,2,3\}=\{a_1,a_2,a_3\}$$$ удовлетворяет этому, таким образом, $$$k_2=6$$$

Обратите внимание, что неиспользуемые наборы, идентичные наборы, многократный вывод одного и того же набора и использование наборов, которые присутствуют изначально, разрешены.