Crate Sorting with the Crane

There are (n) crates waiting to be loaded onto a ship. The crates are numbered (1, 2, \ldots, n) indicating the order in which they should be loaded. Unfortunately, due to a mishap in transit, the crates are arranged in a random order. With limited space at the dock, you need to sort the crates by swapping some of them using a special crane.

The crane is capable of performing a move on any connected interval of crates that has an even length. When a move is applied to an interval ([l, r]) (with (r - l + 1) even), the crane exchanges the first half of the interval with the second half, while keeping the order inside both halves unchanged.

There is an additional constraint: the move counter on the crane is a base-9 integer with at most 6 digits, meaning the crane stops working after (9^6 = 531441) moves. Your sequence of moves must, therefore, not exceed this limit.

Your task is to find a sequence of moves that sorts the crates into increasing order.

inputFormat

The first line contains an integer (n), the number of crates. The second line contains (n) space-separated integers representing the current order of the crates.

outputFormat

The first line should contain a single integer (m), the number of moves. Each of the next (m) lines should contain two integers (l) and (r) (1-indexed) representing a move. For each move, the interval ([l, r]) must have an even length, and applying the move swaps the first half of the interval with the second half.

sample

2
2 1

1
1 2