Problems
Sort from 0 to n - 1
Sort from 0 to n - 1
Given sequence a0
, a1
, ... an-1
of n unique integers, each belongs to the interval [0; n - 1]. The exchange is an operation (i, j) (0 ≤ i, j ≤ n - 1) that swaps the values ai
and aj
. Sort the sequence using the minimum number of exchanges. Print all exchanges.
Input
First line contains number n (n ≤ 106
). Second line contains n different integers from the interval [0; n - 1].
Output
In the first line print the minimum number of exchanges k. In the next k lines print all performed exchanges as pairs (i, j).
Input example #1
3 0 2 1
Output example #1
1 1 2
Input example #2
5 4 0 3 2 1
Output example #2
3 1 4 3 2 4 0