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 ~A~ of size ~N~ containing a permutation of the numbers from ~1~ to ~N~. He allows you to perform the following operation on it:

Select a subarray from index ~L~ to ~R~ ~(1 \le L \le R \le N)~. Consider an array ~B~, containing the elements ~A_L, A_{L+1}, \dots, A_R~ sorted in increasing order. For all ~i~ from ~1~ to ~\lfloor \frac{R-L+1} 2 \rfloor~, swap the position of elements ~B_i~ and ~B_{R-L-i+2}~ in ~A~. 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 ~A~ in increasing order using no more than ~Q~ operations.

Please help Darkness write a program to beat the game for her!

Input Specification

The first line will contain ~2~ integers ~N~ and ~Q~, the size of the given array ~A~ and the number of operations allowed.

The next line will contain ~N~ integers ~A_1, A_2, \dots, A_N~, representing the array ~A~.

Output Specification

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

Then output ~M~ lines each containing two integers ~L_j~ and ~R_j~, representing the subarray on which the ~j~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 ~2N~ operations.

Constraints

For all subtasks:

~1 \le N \le 2\,000~

~1 \le A_i \le N~

~0 \le M \le Q~

~1 \le L_j \le R_j \le N~

All ~A_i~ are pairwise distinct.

Subtask 1 [20%]

~Q = 2 \times N^2~

~1 \le N \le 300~

Subtask 2 [30%]

~Q = 16N~

Subtask 3 [50%]

~Q = 2N~

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 ~A_2, A_3, A_4~. This swaps the ~4~ and the ~6~, changing the array to ~[7, 5, 6, 4, 2, 3, 1]~.

Then you perform the operation on the subarray ~A_2, A_3~. This swaps the ~5~ and the ~6~, changing the array to ~[7, 6, 5, 4, 2, 3, 1]~.

Then you perform the operation on the entire array. This swaps the following pairs: ~(1, 7), (2, 6), (3, 5)~. The array is now ~[1, 2, 3, 4, 6, 5, 7]~.

Finally you perform the operation on the subarray ~A_5, A_6~. This swaps the ~6~ and the ~5~, changing the array to ~[1, 2, 3, 4, 5, 6, 7]~.

Since the final array is sorted in increasing order using no more than ~Q~ 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.