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\}~