题目描述

There are $n$ crates waiting to be loaded onto a ship. The crates are numbered $1 , 2 , \cdots , n$ , the numbers determining the order of loading. Unfortunately, someone messed up the transit and the crates are standing in a row in an arbitrary order. As there is only limited space in the dock area, you must sort the crates by swapping some of them.

You are given a crane that works in the following way: you select a connected interval of crates of even length. The crane then exchanges the first half of the interval with the second half. The order inside both halves remains unchanged. Determine the sequence of crane moves that reorders the crates properly.

The crane's software has a bug: the move counter is a $9-based$ (not $10-based,$ as you might think) integer with at most $6$ digits. Therefore, the crane stops working (and has to be serviced) after $9^{6} = 531441$ moves. Your solution must fit within this limit.

输入格式

The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

Each test case starts with an integer $n , 1 \le n \le 10 000$ , denoting the number of crates. In the next line a permutation of numbers {1 , 2 , \cdots , n} follows.

输出格式

For each test case print a single line containing $m -$ the number of swaps $-$ followed by $m$ lines describing the swaps in the order in which they should be performed. A single swap is described by two numbers $-$ the indices of the first and the last element in the interval to be exchanged. Do not follow the crane's strange software design $-$ use standard decimal numeral system.

题目大意

有 $n$ 个箱子等着装上船。箱子的编号是 $a_1,a_2,\cdots,a_n$。你的工作是通过若干次交换，将它们从小到大排列。你每次可以选择一个区间，将它的前半部分与后半部分交换，两半内部的顺序保持不变。你最多可以交换 $531441$ 次。

输入格式

第一行输入包含数据组数 $T$。

接下来 $2\times T$ 行，表示 $T$ 组数据。每组数据的第一行为 $n\ (1 \leq n \leq 10000)$，表示箱子的数量。第二行为 $n$ 个正整数$a_1,a_2,\cdots,a_n$ ，表示箱子的编号。

输出格式

对于每组数据，首先输出一个数 $m$ ，表示交换的次数。 然后输出 $m$ 行，按照顺序描述每一次交换。对于每次交换，输出要交换的区间中第一个元素和最后一个元素的下标。

2
6
5 4 6 3 2 1
5
1 2 3 4 5

5
1 2
4 5
5 6
4 5
1 6
0

提示

Time limit: 4 s, Memory limit: 128 MB.