您将获得从 $$$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$$$。
如果满足$$$g(A)<f(B)$$$,则可以通过合并两个集合$$$A$$$和$$$B$$$来获得新集合(注意旧集合不会消失)。
正式而言,您可以执行以下操作序列:
- $$$cnt\获取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$$$是集合的ID,你应该确定它)等于$$$\{a_u\mid l_i\leq u\leq r_i\}$$$,即由索引在 $$$l_i$$$ 和 $$$r_i$$$ 之间的所有 $$$a_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$$$ 成对不同) — 给定排列组成。
接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$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$$$ 个所需集合。
请注意大量输出。
示例
输入 #1
3 2 1 3 2 2 3 1 3
输出 #1
6 3 2 1 3 5 2 4 6
输入 #2
2 4 2 1 1 2 1 2 1 2 1 1
输出 #2
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$$$
请注意,未使用的集合、相同的集合、多次输出相同的集合以及使用最初存在的集合都是允许的。