Zenyk and sorting
Limits: 2 sec., 256 MiB
Zenyk has a permutation \(p\) of length \(n\). He wants to sort it using at least number of operations as possible. In one operation Zenyk can swap any two elements. Help Zenyk to minimize the total number of operations.
Input
In first line one integer \(n\) – length of permutation.
In second line \(n\) integers\(p_i\) – elements of permutation.
Output
In first line print one single integer \(k\) – number of operations.
In next \(k\) lines print 2 integers \(i\) and \(j\) – elements to swap.
Constraints
\(1 \le n \le 10^5\).
In this problem there are 5 tests. If \(m\) – optimal number of operations and \(k\) – number of operations in your solution.
If \(k = m\) – you will get 5 points,
if \(k \le 2 \cdot m\) – you will get 4 points,
if \(k \le 3 \cdot m\) – you will get 3 points,
if \(k \le 4 \cdot m\) – you will get 2 points,
if \(k \le 7 \cdot m\) – you will get 1 points,
if \(k > 7 \cdot m\) – you will get 0 points.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 5 3 5 1 4 2 | 2 2 5 3 1 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|