AT_utpc2022_j Divide and Sort

$ (1,2,\ldots,N) $ の順列 $ P = (P_1,P_2,\ldots,P_N) $ が与えられます。あなたは以下の操作を $ 0 $ 回以上 $ 15 $ 回以下行うことができます。 - $ 1\leq l \leq r \leq N $ かつ $ r-l+1 $ が奇数であるような整数組 $ (l,r) $ を選び、数列 $ (P_l,P_{l+1},\ldots,P_r) $ の中央値を $ M $ とする。このとき $ P_x = M $ なる整数 $ x $ が一意に定まる。 $ P $ の $ l $ 番目から $ x-1 $ 番目を（存在すれば）昇順に並び替え、 $ x+1 $ 番目から $ r $ 番目を（存在すれば）昇順に並び替える。 操作によって $ P $ を昇順に並び替えられるか判定し、可能な場合はそのような操作列を一つ求めてください。 中央値とは 長さ $ 2n - 1 $ の数列の中央値は、数列を昇順に並び替えたとき、前から $ n $ 番目の要素の値として定義されます。例えば、 $ (5, 4,2) $ の中央値は $ 4 $ 、 $ (3,1,5,2,4) $ の中央値は $ 3 $ 、 $ (9) $ の中央値は $ 9 $ です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

$ 15 $ 回以下の操作により $ P $ を昇順に並び替えられない場合 $ -1 $ を出力せよ。 そうでない場合、 $ 1 $ 行目に操作を行う回数 $ k $ を出力せよ。ここで $ k $ は $ 0 $ 以上 $ 15 $ 以下の整数でなくてはならない。 次に、 $ k $ 行にわたって操作列を出力せよ。 $ i\ (2\leq i \leq k +1) $ 行目には、 $ i-1 $ 回目の操作で選んだ $ l,r $ を空白区切りで出力せよ。 解が複数存在する場合、どれを出力しても正解とみなされる。

### 部分点 - $ 1 \leq N \leq 7 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ l=1,r=5 $ として操作をします。 数列 $ (2,1,3,5,4) $ の中央値は $ 3 $ であり、 $ P_x=3 $ なる $ x $ は $ 3 $ です。よって $ P $ の $ l=1 $ 番目から $ x-1=2 $ 番目を昇順に並び替え、 $ x+1=4 $ 番目から $ r=5 $ 番目を昇順に並び替えます。 この操作により、 $ P $ は $ (1,2,3,4,5) $ となり確かに昇順に並び替えられています。 ### Sample Explanation 2 $ 15 $ 回以内の操作であれば、操作回数を最小化する必要はありません。 ### Sample Explanation 3 $ 15 $ 回以内の操作で $ P $ を昇順に並び替えられない場合、 $ -1 $ を出力してください。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 2\times 10^5 $ - $ P $ は $ (1,2,\ldots,N) $ の順列