Disqualification

One night, Sam had a terrifying dream. In it, Sam was chased by a permutation of n 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 i and j 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 k 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 k operations that reduces the number of inversions in the given permutation.

Input Format

The first line contains two integers n and k (1 ⩽ n; k ⩽ 10^5) — the number of numbers in the permutation and the number of operations Sam can perform.

The second line contains n integers p[1], p[2], ..., p[n] (1 ⩽ p[i] ⩽ n). It is guaranteed that all numbers are distinct.

Output Format

In the first line, output an integer m (0 ⩽ m ⩽ k) — the number of operations.

In each of the next m lines, output two integers a[i] and b[i] (1 ⩽ a[i], b[i] ⩽ n) — the indices of two adjacent elements of the permutation that need to be swapped.

Examples

Note

In the second example, there are no inversions in the permutation, so no operations are needed.