## Casino Crisis

View as PDF

Points: 12 (partial)
Time limit: 0.5s
Memory limit: 64M

Author:
Problem type

The family of Darkness is once again in financial trouble! To clear off her debt, Darkness decided to go to the country of Elroad with Kazuma to earn some easy cash. However, after a certain someone almost caused the bankruptcy of Elroad, all the luck based games have been replaced with skill based games! Here's the nearest one they found which offers quite a fortune:

The dealer will give you an array of size containing a permutation of the numbers from to . He allows you to perform the following operation on it:

Select a subarray from index to . Consider an array , containing the elements sorted in increasing order. For all from to , swap the position of elements and in . In other words, swap the smallest element of the subarray with the largest element of the subarray, the second smallest element of the subarray with the second largest element of the subarray, and so on, until you reach the median of the subarray.

You win the game if you manage to sort in increasing order using no more than operations.

#### Input Specification

The first line will contain integers and , the size of the given array and the number of operations allowed.

The next line will contain integers , representing the array .

#### Output Specification

On the first line output one integer , the number of operations used. This number should not exceed .

Then output lines each containing two integers and , representing the subarray on which the th operation is performed.

Note: You do not need to find the shortest sequence of operations to sort the array. If there are multiple valid solutions, output any of them. Also, it can be proven that it is always possible to sort the array using no more than operations.

#### Constraints

All are pairwise distinct.

#### Sample Input

7 98
7 5 4 6 2 3 1

#### Sample Output

4
2 4
2 3
1 7
5 6

#### Explanation

First you perform the operation on the subarray . This swaps the and the , changing the array to .

Then you perform the operation on the subarray . This swaps the and the , changing the array to .

Then you perform the operation on the entire array. This swaps the following pairs: . The array is now .

Finally you perform the operation on the subarray . This swaps the and the , changing the array to .

Since the final array is sorted in increasing order using no more than operations, Darkness wins and is once again debt free!

Note that the sample output is not the only possible output which will receive AC for this case.