Can you sort the bubbles by increasing bubble radius using bubble sort?

Since the Canadian Computing Competition (CCC) often requires the use of a sorting algorithm, Darcy needs to practice sorting! Darcy's favourite sorting algorithm is bubble sort.

To practice his ability to bubble sort, he gathers up an array $A$ which contains $N$ integers. He accesses this array by calling $A[0]$ as the first element, and $A[N-1]$ as the last element. Every element in this array is an integer in the range $0\dots N-1$, and there are no duplicate elements.

Darcy swaps adjacent elements to sort this array, but if $A[x]=x$, he does not want to swap the integer $x$ ever again. Specifically, Darcy is allowed to swap the elements $A[i]$ and $A[i+1]$ if these following conditions hold:

• The first index is valid ($0\le i\le N-1$)
• The second index is valid ($0\le i+1\le N-1$)
• Darcy can swap the element at the first index ($A[i]\ne i$)
• Darcy can swap the element at the second index ($A[i+1]\ne i+1$)

Eventually, Darcy gets confused and asks for help. Is there a sequence of swaps that will sort $A$? In the case that no sequence exists, output Give up.

Input Specification

The first line contains the integer $N$ $(1\le N\le 1500)$.

The second line contains $N$ space-separated integers, which are the elements of $A$. These integers are between $0$ and $N-1$, inclusive. Every element in the array is distinct.

• For 3 of the 15 available marks, the elements of $A$ are in descending order.
• For an additional 2 of the 15 available marks, all multiples of $6$ are put in the correct index. Specifically, $A[6x]=6x$.
• For an additional 2 of the 15 available marks, $1\le N\le 6$.
• For an additional 4 of the 15 available marks, $1\le N\le 100$.

Output Specification

If it is impossible to sort the array $A$, output Give up.

Otherwise, output the number of swaps needed to sort the array. Let this number be called $S$. Your integer $S$ must not exceed $2$ million ($=2\times {10}^5\times 10$). You do not have to print the lowest possible $S$.

On the next $S$ lines of output, print two indices $i$ and $j$. This indicates that $A[i]$ and $A[j]$ will be swapped in this step.

Sample Input 1

2
0 1

Sample Output 1

0

Explanation for Sample Output 1

The array is already sorted, so no swaps are necessary.

Sample Input 2

5
4 3 2 1 0

Sample Output 2

Give up

Explanation for Sample Output 2

Darcy does not want to swap the integer $2$ because $A[2]=2$. As a result, the remaining integers cannot be swapped to their proper indices. This array is impossible to sort.

Sample Input 3

6
2 5 1 4 0 3

Sample Output 3

13
3 2
3 2
3 2
4 3
1 2
2 3
3 4
4 5
1 2
2 3
3 4
0 1
1 2

Explanation for Sample Output 3

The table shows array $A$ as the $13$ instructions are performed. Notice that the bubble sort algorithm can be used after the $4^{\text{th}}$ swap.

Instruction number	Indices	Array $A$
$0$	-	$\{2,5,1,4,0,3\}$
$1$	$3,2$	$\{2,5,4,1,0,3\}$
$2$	$3,2$	$\{2,5,1,4,0,3\}$
$3$	$3,2$	$\{2,5,4,1,0,3\}$
$4$	$4,3$	$\{2,5,4,0,1,3\}$
$5$	$1,2$	$\{2,4,5,0,1,3\}$
$6$	$2,3$	$\{2,4,0,5,1,3\}$
$7$	$3,4$	$\{2,4,0,1,5,3\}$
$8$	$4,5$	$\{2,4,0,1,3,5\}$
$9$	$1,2$	$\{2,0,4,1,3,5\}$
$10$	$2,3$	$\{2,0,1,4,3,5\}$
$11$	$3,4$	$\{2,0,1,3,4,5\}$
$12$	$0,1$	$\{0,2,1,3,4,5\}$
$13$	$1,2$	$\{0,1,2,3,4,5\}$