#216986. [ICPC 2025 Shanghai R] Singularity

In the year of , problemsetting becomes simple. Robots will generate a problem by setting some random operations and then solve it. A problemsetter only has to check whether the problem is correct or not.

Here is a problem from :

Given a permutation , it is guaranteed that is even. You wish to sort the permutation, using only one type of operation:

• FakeSort(l,r): You have to guarantee that is even. Let , then the largest elements and the smallest elements in the continuous subsequence will be sorted independently. That is, let be the indices of the largest numbers, and be the indices of the smallest numbers. We first sort the numbers on the indices , then sort the numbers on the indices .

Here is a concrete example; suppose the permutation is . If we call FakeSort(2,7):

• . The continuous subsequence is ; we will sort the largest numbers and smallest numbers of this sequence independently.

• ; the largest numbers are bold. After sorting, they become .

• ; the smallest numbers are bold. After sorting, they become .

So after FakeSort(2,7) becomes .

Please use no more than operations to sort the permutation or determine it is impossible. It can be proved that if a permutation can be sorted with this operation, there is a way to use no more than operations.

The input contains multiple testcases. The first line of the input contains an integer (), the number of testcases.

For each testcase, the first line contains an even integer (), the length of the permutation.

The second line contains integers (), the permutation you need to sort. It is guaranteed that is a permutation.

It’s guaranteed that the sum of over all testcases does not exceed .

For each testcase, if it is impossible to sort the permutation, print -1.

Otherwise, print an integer (), denoting the number of operations used.

In the following lines, print ( is even) in each line, denoting performing Fakesort(l,r).

样例输入 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