Disqualification#8778
One night, Sam had a terrifying dream. In it, Sam was chased by a permutation of numbers, which ominously spoke about a programming olympiad.
After recounting this dream to Yura, they consulted a dream interpretation book and discovered that such a dream could only mean one thing: the number of strong teams in the olympiad would be exactly equal to the number of inversions in the permutation. Recall that an inversion in a permutation is a pair of indices and such that i < j and p_i > p_j.
Realizing there were quite a few inversions in the permutation, Sam knew this was unacceptable. With his supernatural abilities, Sam can revisit this dream and adjust the permutation slightly to minimize the number of strong teams in the olympiad. Sam has time for only operations, and in each operation, he can swap any two adjacent elements of the permutation.
Help Sam minimize the number of strong teams in the olympiad by finding a sequence of no more than operations that reduces the number of inversions in the given permutation.
The first line contains two integers and (1 \leq n;\ k \leq 10^5) — the number of numbers in the permutation and the number of operations Sam can perform.
The second line contains integers p_1,\ p_2,\ \dots,\ p_n (1 \leq p_i \leq n). It is guaranteed that all numbers are distinct.
In the first line, output an integer (0 \leq m \leq k) — the number of operations.
In each of the next lines, output two integers a_i and b_i (1 \leq a_i,\ b_i \leq n) — the indices of two adjacent elements of the permutation that need to be swapped.
Example 1
Example 2
In the second example, there are no inversions in the permutation, so no operations are needed.