When you are running from a bear that wants to play with you and/or consume you for dinner, it is very important to recognize its species: if you run and run, find a tree and climb it, and the bear follows you, it is a brown bear, if you run and run, find a tree and climb it, and the bear shakes you off it, it is a grizzly bear, * if you run and run and cannot find a tree, it is a polar bear.

Let us focus on finding a tree. In computer science, a tree is simply a set of $k$ vertices and $k-1$ edges, where each edge connects two vertices. The connections must guarantee that every vertex can be reached from every other vertex by moving only along the edges. The number of edges connected to a vertex is called the degree of that vertex.

You are given a sequence of $n$ numbers $a_1, a_2, \dots, a_n$. You suspect that this is a list of the degrees of all vertices of some tree. Unfortunately, some random numbers have become entangled in the sequence, and some others have been incorrectly transcribed along the way. Remove the unnecessary numbers from the sequence and change some others so that it is actually a valid list of degrees.

Formally, you can change the order of the elements of the given sequence of $n$ numbers, remove some of them, and then change some of the remaining elements. For the resulting sequence of numbers $d_1, d_2, \dots, d_k$, you must provide a tree with $k \ge 2$ vertices (numbered from 1 to $k$) such that $d_i$ is the degree of the $i$-th vertex. Both the number of removed and changed vertices can be arbitrary (including 0) — your task is to find a solution with the minimum number of changed vertices.

Input

The first line of input contains an integer $n$ ($2 \le n \le 10^6$) — the number of elements in the sequence. The next line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n - 1$).

Output

In the first line, print the number of changed elements $x$ (you must minimize this value). In the second line, print the size of the tree $k$ ($2 \le k \le n$). In each of the next $k-1$ lines, print two numbers $u_i$ and $v_i$ ($1 \le u_i, v_i \le k$), describing an edge between vertices $u_i$ and $v_i$. The printed edges must form a tree.

If there are multiple solutions, print any one of them. You do not need to minimize or maximize the value of $k$.

Examples

Input 1

6
2 1 5 3 1 1

Output 1

0
5
1 2
2 3
1 4
1 5

Note

In the given sequence, we can remove the number 5 and change the order of the remaining numbers to 3, 2, 1, 1, 1. The output shows $x = 0$ (we do not modify any value) in the first line, and the description of a tree with $k = 5$ vertices in the following lines. The printed tree has exactly the same degrees as above.

Input 2

3
1 2 2

Output 2

1
3
1 2
2 3

Note

This time, removing elements is not enough. We can change the sequence 1, 2, 2 to 1, 2, 1, which gives $x = 1$. This is an optimal solution (the smallest possible number of changes $x$).

Subtasks

In some test groups (at least one), it is not necessary to change any elements, meaning that in the optimal solution $x = 0$.

Testy

Ze względu na specyfikę zadania, jurorzy podjęli decyzję, że w przypadku tego zadania na forum nie można dzielić się testami. W dziale Pliki można znaleźć za to paczkę z kilkoma testami przygotowanymi przez jurorów.