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)

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.

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)

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