CF1375H Set Merging

给定一个长度为 $n$ 的排列 $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)

第一行包含两个整数 $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$ 行，每行包含两个整数 $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)

在第一个样例中： 初始时有 $S_1=\{1\},S_2=\{3\},S_3=\{2\}$。 第一次操作，因为 $g(S_3)=2