Problem Statement

Given a permutation of length $n$, $p_1, p_2, p_3, \dots, p_n$, you can perform an operation where you swap two elements $p_i$ and $p_j$, with $1 \leq i , j \leq n$.

Your task is to sort the permutation in ascending order $1, 2, 3, \dots, n$ in at most $n - 1$ operations. You need to output a sequence of operations that achieves this.

Input

The first line contains an integer $n$, the length of the permutation $(2 \leq n \leq 10^6)$.

The second line contains $n$ integers $p_1, p_2, p_3, \dots, p_n$, representing the given permutation. It is guaranteed that each integer from $1$ to $n$ appears exactly once.

Output

On the first line, output an integer $k$, the number of operations required.

In the following $k$ lines, output two integers $x$ and $y$ per line, indicating a swap between $p_x$ and $p_y$ $(1 \leq x , y \leq n)$.

Example

Input

5
3 4 1 5 2

Output

3
1 3
2 4
5 2

Constraints

• For all inputs, $2 \leq n \leq 10^6$.
• There may be multiple valid solutions; you only need to output one solution that satisfies the conditions.

To handle large input and output efficiently, you can use faster I/O methods in C++.

In C++, you can use the following lines at the beginning of your main function:

ios::sync_with_stdio(false);
cin.tie(nullptr);

This will speed up I/O operations by disabling the synchronization between C++ and C I/O streams and untie cin from cout, making cin operate independently of cout.