Valera and Swaps

Description:

Input:

The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers p₁, p₂, ..., p_n (1 ≤ p_i ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m < n).

Output:

In the first line, print integer k — the minimum number of swaps.

In the second line, print 2k integers x₁, x₂, ..., x_2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x₁, x₂), (x₃, x₄), ..., (x_2k - 1, x_2k).

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

Sample Input:

5
1 2 3 4 5
2

Sample Output:

2
1 2 1 3 

Sample Input:

5
2 1 4 5 3
2

Sample Output:

1
1 2 

Note:

Sequence x₁, x₂, ..., x_s is lexicographically smaller than sequence y₁, y₂, ..., y_s, if there is such integer r (1 ≤ r ≤ s), that x₁ = y₁, x₂ = y₂, ..., x_r - 1 = y_r - 1 and x_r < y_r.