Вам дана перестановка \(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)\) (обратите внимание, что старые множества не исчезают).
Формально, вы можете выполнить следующую последовательность операций:
Вам необходимо получить некоторые конкретные множества.
Существуют \(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\). Гарантируется, что решение при данных ограничениях существует.
Выходные данные
Гарантируется, что решение при данных ограничениях существует.
Первая строка должна содержать одно целое число \(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\)-м необходимым набором.
Пожалуйста, обратите внимание на большое количество вывода.
Примечание
В первом примере:
Изначально у нас есть \(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\)
Обратите внимание, что неиспользуемые наборы, идентичные наборы, многократный вывод одного и того же набора и использование наборов, которые присутствуют изначально, разрешены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 2
2 3
1 3
|
6
3 2
1 3
5 2
4 6
|
|
2
|
2 4
2 1
1 2
1 2
1 2
1 1
|
5
2 1
2 1
2 1
5 3 3 1
|