Permutation Sorting by Special Reordering Operation

You are given a permutation \( [a_1, a_2, \ldots, a_n] \) of \( n \) integers.

An operation \( S(l, r) \) is defined as reordering the subarray \( [a_l, a_{l+1}, \ldots, a_r] \) into \( [a_{l+1},a_{l+3},\ldots,a_l,a_{l+2},\ldots] \). In other words, if you denote the subarray as \( [x_0,x_1,x_2,x_3,\ldots] \) (where \( x_0=a_l,x_1=a_{l+1},\) etc.), after the operation the segment becomes the concatenation of \( [x_1,x_3,x_5,\ldots] \) and \( [x_0,x_2,x_4,\ldots] \).

For example, applying \( S(2,6) \) to the array [2, 4, 1, 5, 3, 6, 7, 8] transforms the subarray \( [4, 1, 5, 3, 6] \) into \( [1, 3, 4, 5, 6] \), resulting in the array [2, 1, 3, 4, 5, 6, 7, 8].

Your task is to find a sequence of operations that will sort the given permutation in strictly increasing order. You do not need to minimize the number of operations, but the total number of operations must be at most 15000. If the permutation is already sorted, output 0 (with no additional operations).

inputFormat

The first line contains an integer \( n \), representing the size of the permutation. The second line contains \( n \) space-separated integers \( a_1,a_2,\ldots,a_n \), which form a permutation of \( \{1, 2, \ldots, n\} \).

outputFormat

First, output an integer \( k \) indicating the number of operations performed. Then output \( k \) lines, each containing two integers \( l \) and \( r \) (1-indexed) representing an operation \( S(l, r) \).

sample

3
1 2 3

0