2077 年、作問は簡単になります。ロボットがランダムな操作を設定して問題を生成し、それを自ら解くのです。作問者は、その問題が正しいかどうかを確認するだけで済みます。
以下は 2077 年から届いた問題です：
順列 $p_1, p_2, \dots, p_n$ が与えられます。$n$ は偶数であることが保証されています。次の種類の操作のみを用いて、この順列をソートしたいです：
FakeSort(l,r)：$r - l + 1$ が偶数であることを保証しなければなりません。$k = r - l + 1$ とすると、連続部分列 $p_l, p_{l+1}, \dots, p_r$ のうち大きい方から $k/2$ 個の要素と小さい方から $k/2$ 個の要素がそれぞれ独立にソートされます。すなわち、大きい方から $k/2$ 個の数の添字を $L_1, L_2, \dots, L_{k/2}$、小さい方から $k/2$ 個の数の添字を $S_1, S_2, \dots, S_{k/2}$ とします。まず添字 $L_1 \sim L_{k/2}$ にある数をソートし、次に添字 $S_1 \sim S_{k/2}$ にある数をソートします。
具体例を挙げます。順列を $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ とします。ここで FakeSort(2,7) を呼び出すと：
- $k = r - l + 1 = 6$ です。連続部分列 $p_l, p_{l+1}, \dots, p_r$ は $\{5, 7, 1, 8, 6, 4\}$ であり、この列の大きい方から $3$ 個の数と小さい方から $3$ 個の数をそれぞれ独立にソートします。
- $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$。大きい方から $3$ 個の数が太字になっています。ソート後、それらは $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$ になります。
- $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$。小さい方から $3$ 個の数が太字になっています。ソート後、それらは $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$ になります。
したがって、$p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ は FakeSort(2,7) の後に $\{2, 1, 6, 4, 7, 8, 5, 3\}$ となります。
$114$ 回以下の操作を用いて順列をソートするか、ソート不可能であると判定してください。この操作で順列をソートできるならば、$114$ 回以下の操作でソートする方法が存在することが証明できます。
入力
入力は複数のテストケースからなります。入力の最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^3$）が与えられます。
各テストケースについて、最初の行には順列の長さを表す偶数の整数 $n$（$4 \le n \le 10^5$）が与えられます。
次の行には、ソートすべき順列を表す $n$ 個の整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）が与えられます。$p$ が順列であることは保証されています。
すべてのテストケースにおける $n$ の総和は $2 \times 10^5$ を超えないことが保証されます。
出力
各テストケースについて、順列をソートすることが不可能な場合は $-1$ を出力してください。
そうでない場合は、使用する操作の回数を表す整数 $k$（$0 \le k \le 114$）を出力してください。
続く $k$ 行には、各行に FakeSort(l,r) を実行することを表す $l, r$（$1 \le l \le r \le n$、かつ $r - l + 1$ は偶数）を出力してください。
入出力例
入力例 1
3 4 2 1 4 3 6 3 6 5 1 2 4 8 3 2 1 7 5 4 6 8
出力例 1
1 1 4 -1 2 4 7 1 6