Strange Permutation Sorting

You are given a permutation (a_1, a_2, \ldots, a_n) of ({1,2,\ldots,n}). You need to sort the permutation in ascending order (i.e. make (a_i=i) for all (i)) using the following operation any number of times:

• Choose two indices \(i\) and \(j\) satisfying \(1 \le i, j \le n\) and \(|j-i|>1\), then swap \(a_i\) and \(a_j\).

Print a sorting scheme that uses the minimum number of operations to sort the permutation, or report that it is impossible. If there are multiple optimal solutions, output any one.

Note: The identity (sorted order) is considered to be already sorted and requires 0 operations.

Important Observation on Parity: Each allowed swap is a transposition (an odd permutation). Thus, if a permutation is unsorted, it can be sorted only if the parity of the permutation matches the parity of a product of allowed swaps. In other words, if a single allowed swap is used then the input permutation must be odd (since a transposition is odd and the identity permutation is even). In general, if the minimal number of swaps is (k), then ((-1)^k) must equal the sign of the input permutation. Also note that when (n=2) the only possible pair of indices are adjacent and when (n=3) the only allowed pair is ((1,3)). Therefore, for (n=2) and some cases in (n=3) the answer may be impossible.

Input Constraints: You may assume that (n) is small (e.g. (n\le 6)) so that a BFS search over the state space (of at most (n!) states) is feasible.

Input Format:

• The first line contains an integer \(n\) (\(1\le n\le 6\)).
• The second line contains \(n\) space separated integers \(a_1, a_2, \dots, a_n\) -- a permutation of \(\{1,2,\ldots,n\}\).

Output Format:

• If the permutation is already sorted, output a single line containing 0.
• If it is impossible to sort the permutation using the allowed operation, output -1.
• Otherwise, on the first line output an integer \(k\) representing the minimum number of operations. Then output \(k\) lines, each containing two integers \(i\) and \(j\) (1-indexed) indicating that you swap \(a_i\) and \(a_j\) in that operation.

Example: If the input is:

3
3 2 1

Then one valid output is:

1
1 3

Because swapping the first and the third elements yields the sorted permutation [1, 2, 3].

inputFormat

The first line contains a positive integer (n) ((1 \le n \le 6)). The second line contains (n) distinct integers (a_1, a_2, \ldots, a_n) which is a permutation of ({1,2,\ldots,n}).

outputFormat

If the permutation is already sorted, output 0. If it is impossible to sort using the allowed swap (i.e. no sequence of allowed moves exists), output -1. Otherwise, first output an integer (k) (the least number of operations), followed by (k) lines each containing two integers (i) and (j) (1-indexed) denoting that you swap (a_i) and (a_j).

sample

2
1 2

0