Strange Computer Permutation Sorting

You are given a permutation of the integers \(1\) to \(n\). On a strange computer, you can perform reversal operations to sort the permutation. At the beginning, you must choose an integer \(x\). Then, in each move, you are allowed to reverse any contiguous subsequence of the permutation whose length is either \(x+1\) or \(x-1\). Your task is to sort the permutation in ascending order (i.e. transform it into \(1,2,\ldots,n\)) by performing at most \(20\times n\) moves.

Important: All formulas must be formatted in LaTeX. For example, the allowed reversal lengths are \(x+1\) and \(x-1\), and the move limit is \(20\times n\).

Note from the author: Current best solutions can sort the permutation in fewer than 15000 moves. Try to optimize your algorithm!

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) \((1 \le n \le 100)\), which represents the number of elements in the permutation. The second line contains \(n\) space-separated integers representing the permutation of \(1,2,\ldots,n\>.

outputFormat

First, print the chosen integer \(x\) on a single line. Then, on the next line, print an integer \(k\) representing the number of moves you performed. The following \(k\) lines should each contain two integers \(i\) and \(L\) (1-indexed), indicating that you reversed the subarray starting at position \(i\) of length \(L\). Note that \(L\) must be either \(x+1\) or \(x-1\), and it is guaranteed that \(i+L-1 \le n\).

If the given permutation is already sorted, you should output \(x\) followed by 0 on the next line.

sample

4
1 2 3 4

3
0