Xiao R and Xiao C were so intimidated after hearing about a computer architecture course in their department that they submitted their withdrawal applications overnight.

Just kidding! As freshmen, they are not afraid of this course at all; in fact, they find it quite amusing. Their strong hands-on ability even drove them to want to build something for fun.

Of course, since they are only freshmen and haven't taken any professional computer science courses, after a long and arduous struggle, they finally built a strange contraption:

This computer has only $n$ memory units, but it has a sufficient number of registers. The memory units are numbered from $1$ to $n$, and the registers are numbered starting from $n+1$ upwards. Each memory unit and register can store an integer.

They have already designed a type of instruction: swap i, j, which swaps the numbers in the units numbered $i$ and $j$, where $i$ and $j$ are both positive integers and $i \neq j$. They intend to write a program to test this instruction.

Initially, the $n$ memory units contain the numbers $1 \sim n$ in a random order, with each number appearing exactly once. Each register contains its own index number.

The two plan to design a sequence of instructions such that after the computer executes these instructions in order, all numbers in the memory and registers are in their correct positions, meaning each unit contains the number equal to its own index.

Although they haven't taken professional computer science courses, Xiao R and Xiao C know a little bit, so they stipulated that at least one of the two positions operated by each swap instruction must be a register; that is, at least one of $i$ and $j$ must be greater than $n$.

However, just as they finished writing the program and started running it, the system crashed! After searching for the cause for a long time, they discovered a strange bug: the computer they designed cannot execute two identical instructions! In other words, they cannot have two identical swap i, j instructions in a single program. Furthermore, they found that even having one swap i, j and one swap j, i is not allowed, because the computer automatically treats these two instructions as the same.

Poor Xiao R and Xiao C were devastated. However, before giving up, they still intended to use the existing architecture to write the program. Moreover, they hope to use as few registers as possible. Can you help them?

Input

Read data from standard input.

The first line contains a positive integer $n\ (1 \leq n \leq 10^5)$, representing the number of memory units.

The second line contains $n$ positive integers $a_i$, representing the initial values in the $i$-th memory unit, guaranteed to be a permutation of $1 \sim n$.

Output

Output to standard output.

The first line contains two non-negative integers $m$ and $k$, representing the number of registers used and the number of instructions, respectively.

The next $k$ lines each contain two positive integers $i, j$, representing the two positions swapped by each instruction in the order they are designed. You must ensure $1 \leq i, j \leq n+m$ and satisfy the constraints on the instructions given in the problem.

If there are multiple ways to design the instructions that satisfy the requirements, you may output any one of them.

You need to minimize $m$ without needing to minimize $k$, but you must ensure $k \leq 10^6$. The input data guarantees that a valid solution exists.

Examples

Input 1

2
2 1

Output 1

2 5
3 4
1 3
2 4
1 4
2 3

Note 1

Initially, the values of the first $4$ units are $(2, 1, 3, 4)$.

Executing swap 3, 4 changes the values to $(2, 1, 4, 3)$.

Executing swap 1, 3 changes the values to $(4, 1, 2, 3)$.

Executing swap 2, 4 changes the values to $(4, 3, 2, 1)$.

Executing swap 1, 4 changes the values to $(1, 3, 2, 4)$.

Executing swap 2, 3 changes the values to $(1, 2, 3, 4)$.

It can be proven that $m=1$ is not sufficient.