#593 Swap Two Elements

Loading problem...

Preparing the statement, recent submissions, and submit form.

DOJ/Beginner Contest DOJ/BCD 8

Time limit: 3000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

You are given a permutation $A=[A_1,A_2,\cdots,A_N]$ . You may perform the following operation any number of times.

Choose integers $i,j$ with $1\leq i<j\leq N$ .
In the subarray $A_i,A_{i+1},\cdots,A_j$ , swap the positions containing the smallest and the second-smallest values.

Print the minimum number of operations required to sort the permutation in increasing order and one sequence of operations attaining that minimum.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

For each test case, first print the minimum number of operations $Q$ .

Then print $Q$ lines containing the chosen $i,j$ for each operation in order. If there are multiple optimal sequences, print any of them.

Constraints

$1 \leq T \leq 1\,000$ .
$1 \leq N \leq 1\,000$ .
$A$ is a permutation of $1,2,\cdots,N$ .
The sum of $N$ over all test cases does not exceed $1\,000$ .

Subtasks

#	Score	Constraints
1	9	$N \leq 8$ . The sum of $N$ over all test cases does not exceed $800$ .
2	18	The initial permutation has at most one inversion in each test case.
3	73	No additional constraints.

Samples

Input

1
4
1 3 2 4

Output

1
2 3

The elements in the interval $[2,3]$ are $3$ and $2$ . Swapping the positions of the smallest and second-smallest elements in this interval changes the permutation to $(1,2,3,4)$ . Since the original permutation is not sorted, the minimum number of operations is $1$ .

Editorial

View editorial