AT_abc431_g [ABC431G] One Time Swap 2

長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 整数の組 $ (l, r) \ (1\leq l\lt r\leq N) $ に対し、 $ f(l,r) $ を「 $ A $ の $ l $ 番目の要素と $ r $ 番目の要素を入れ替えることで得られる整数列」とします。 長さ $ \frac{N(N-1)}{2} $ の整数列の列 $ B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) $ を次の手順で生成します。 - 空の列 $ B=() $ を用意する。 - 各整数の組 $ (l, r)\ (1\leq l\lt r\leq N) $ に対し、 $ B $ に $ f(l,r) $ を追加する。 - $ B $ を数列の辞書順でソートする。 $ Q $ 個のクエリが与えられるので、順に処理してください。 $ i $ 番目のクエリは以下の通りです。 - 整数 $ k $ が与えられる。 $ B_k=f(l,r) $ となるような整数の組 $ (l, r) \ (1\leq l\lt r\leq N) $ を一つ求めそれを出力せよ。 数列の辞書順とは？数列 $ S = (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T = (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、 $ |S|, |T| $ はそれぞれ $ S, T $ の長さを表します。 1. $ |S| \lt |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ 。 2. ある整数 $ 1 \leq i \leq \min\lbrace |S|, |T| \rbrace $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ が $ T_i $ より（数として）小さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ k $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを以下の形式で出力せよ。 > $ l $ $ r $ 答えが複数存在する場合、どれを出力しても正解とみなされる。

### Sample Explanation 1 $ f(1, 2) = (2, 1, 1, 2), f(1, 3) = (1, 2, 1, 2), f(1, 4) = (2, 2, 1, 1), f(2, 3) = (1, 1, 2, 2), f(2, 4) = (1, 2, 1, 2), f(3, 4) = (1, 2, 2, 1) $ です。 これら $ 6 $ つの数列を辞書順でソートした列 $ B $ は $ B=((1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)) $ です。 - $ 1 $ 番目のクエリについて、 $ B_1=(1,1,2,2)=f(l,r) $ が成り立つような $ (l,r) $ は $ (l,r)=(2,3) $ のみです。 - $ 2 $ 番目のクエリについて、 $ B_3=(1,2,1,2)=f(l,r) $ が成り立つような $ (l,r) $ は $ (l,r)=(1,3),(2,4) $ です。この場合、どちらを出力しても正解とみなされます。 - $ 3 $ 番目のクエリについて、 $ B_5=(2,1,1,2)=f(l,r) $ が成り立つような $ (l,r) $ は $ (l,r)=(1,2) $ のみです。 ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq Q\leq 2\times 10^5 $ - $ 1\leq A_i\leq N $ - $ 1\leq k\leq \frac{N(N-1)}{2} $ - 入力は全て整数