問題文

(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 を昇順に並び替えられるか判定し、可能な場合はそのような操作列を一つ求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 2\times 10^5
• P は (1,2,\ldots,N) の順列

部分点

• 1 \leq N \leq 7 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

5
2 1 3 5 4

出力例 1

1
1 5

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) となり確かに昇順に並び替えられています。

入力例 2

4
1 2 3 4

出力例 2

2
1 3
2 4

15 回以内の操作であれば、操作回数を最小化する必要はありません。

入力例 3

2
2 1

出力例 3

-1

15 回以内の操作で P を昇順に並び替えられない場合、 -1 を出力してください。