CF1375H.Set Merging

You are given a permutation $a_1, a_2, \dots, a_n$ of numbers from $1$ to $n$. Also, you have $n$ sets $S_1,S_2,\dots, S_n$, where $S_i={a_i}$. Lastly, you have a variable $cnt$, representing the current number of sets. Initially, $cnt = n$.

We define two kinds of functions on sets:

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

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

You can obtain a new set by merging two sets $A$ and $B$, if they satisfy $g(A) \lt f(B)$ (Notice that the old sets do not disappear).

Formally, you can perform the following sequence of operations:

• $cnt\gets cnt+1$;

• $S_{cnt}=S_u\cup S_v$, you are free to choose $u$ and $v$ for which $1\le u, v \lt cnt$ and which satisfy $g(S_u) \lt f(S_v)$.

You are required to obtain some specific sets.

There are $q$ requirements, each of which contains two integers $l_i$,$r_i$, which means that there must exist a set $S_{k_i}$ ($k_i$ is the ID of the set, you should determine it) which equals ${a_u\mid l_i\leq u\leq r_i}$, which is, the set consisting of all $a_i$ with indices between $l_i$ and $r_i$.

In the end you must ensure that $cnt\leq 2.2\times 10^6$. Note that you don't have to minimize $cnt$. It is guaranteed that a solution under given constraints exists.

给你一个 $1$ 到 $n$ 的排列 $a_1, a_2, \dots, a_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$，其中你可以自由选择满足 $1 \le u, v < cnt$ 且 $g(S_u) < f(S_v)$ 的下标 $u$ 和 $v$。

你需要获得若干特定的集合。

共有 $q$ 个要求，每个要求包含两个整数 $l_i$、$r_i$，表示必须存在某个集合 $S_{k_i}$（$k_i$ 是该集合的编号，由你确定），使得 $S_{k_i} = \{a_u \mid l_i \leq u \leq r_i\}$，即该集合恰好包含下标在 $l_i$ 到 $r_i$ 之间的所有 $a_i$。

最终你必须保证 $cnt \leq 2.2 \times 10^6$。注意：你无需最小化 $cnt$。题目保证在给定约束下存在解。

The first line contains two integers $n,q$ $(1\leq n \leq 2^{12},1 \leq q \leq 2^{16})$ — the length of the permutation and the number of needed sets correspondently.

The next line consists of $n$ integers $a_1,a_2,\cdots, a_n$ ($1\leq a_i\leq n$, $a_i$ are pairwise distinct) — given permutation.

$i$-th of the next $q$ lines contains two integers $l_i,r_i$ $(1\leq l_i\leq r_i\leq n)$, describing a requirement of the $i$-th set.

第一行包含两个整数 $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$ 两两不同）—— 给定的排列。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i,r_i$（$1\leq l_i\leq r_i\leq n$），描述第 $i$ 个集合的要求。

It is guaranteed that a solution under given constraints exists.

The first line should contain one integer $cnt_E$ $(n\leq cnt_E\leq 2.2\times 10^6)$, representing the number of sets after all operations.

$cnt_E-n$ lines must follow, each line should contain two integers $u$, $v$ ($1\leq u, v\leq cnt'$, where $cnt'$ is the value of $cnt$ before this operation), meaning that you choose $S_u$, $S_v$ and perform a merging operation. In an operation, $g(S_u) \lt f(S_v)$ must be satisfied.

The last line should contain $q$ integers $k_1,k_2,\cdots,k_q$ $(1\leq k_i\leq cnt_E)$, representing that set $S_{k_i}$ is the $i$th required set.

Please notice the large amount of output.

在给定约束下，保证存在解。

第一行应包含一个整数 $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) \lt f(S_v)$。

最后一行应包含 $q$ 个整数 $k_1,k_2,\cdots,k_q$（$1\leq k_i\leq cnt_E$），表示集合 $S_{k_i}$ 是第 $i$ 个所要求的集合。

请注意输出量较大。

In the first sample:

We have $S_1={1},S_2={3},S_3={2}$ initially.

In the first operation, because $g(S_3)=2 \lt f(S_2)=3$, we can merge $S_3,S_2$ into $S_4={2,3}$.

In the second operation, because $g(S_1)=1 \lt f(S_3)=2$, we can merge $S_1,S_3$ into $S_5={1,2}$.

In the third operation, because $g(S_5)=2 \lt f(S_2)=3$, we can merge $S_5,S_2$ into $S_6={1,2,3}$.

For the first requirement, $S_4={2,3}={a_2,a_3}$, satisfies it, thus $k_1=4$.

For the second requirement, $S_6={1,2,3}={a_1,a_2,a_3}$, satisfies it, thus $k_2=6$

Notice that unused sets, identical sets, outputting the same set multiple times, and using sets that are present initially are all allowed.

在第一个样例中：

初始时，我们有 $S_1={1},S_2={3},S_3={2}$。

第一次操作：因为 $g(S_3)=2 \lt f(S_2)=3$，我们可以将 $S_3$ 与 $S_2$ 合并为 $S_4={2,3}$。

第二次操作：因为 $g(S_1)=1 \lt f(S_3)=2$，我们可以将 $S_1$ 与 $S_3$ 合并为 $S_5={1,2}$。

第三次操作：因为 $g(S_5)=2 \lt 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$。

注意：允许使用未被使用的集合、重复的集合、多次输出同一集合，以及使用初始时已存在的集合。