Problem Description

This problem is translated from PA 2018 Round 1 Poddrzewo.

You are given a sequence $a$ of length $n$.

Construct an undirected tree with $k$ nodes, numbered $1 \cdots k$. The degree of node $i$ in this tree must be $a_i$.

A solution may not exist. You are allowed to perform the following operations to make it solvable:

1. Modify the $i$-th number in the sequence.
2. Delete the $i$-th number from the sequence.
3. Swap the $i$-th and $j$-th numbers in the sequence.

It can be proven that after a finite number of operations, a solution will always exist.

Your task is to minimize the number of times operation 1 is used.

Input Format

The first line contains an integer $n$, the length of the sequence $a$.

The second line contains $n$ integers. The $i$-th integer is $a_i$.

Output Format

The first line contains an integer $x$, the minimum number of times operation 1 is used.

The second line contains an integer $k\ (2 \le k \le n)$, the number of nodes in the tree you construct.

In the next $k - 1$ lines, each line contains two integers $u, v\ (1 \le u, v \le k)$, indicating an edge between nodes $u$ and $v$.

If there are multiple solutions, output any one.

6
2 1 5 3 1 1

0
5
1 2
2 3
1 4
1 5

3
1 2 2

1
3
1 2
2 3

Hint

Explanation for Sample 1

We can delete the $3$-rd number and then change the order of the elements.

The final sequence becomes $(3,2,1,1,1)$.

This is a schematic diagram of the constructed tree:

Explanation for Sample 2

We can modify the $3$-rd number, and the final sequence becomes $(1,2,1)$. It can be proven that operation 1 must be used at least $1$ time.

This is a schematic diagram of the constructed tree:

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata:

• $2 \le n \le 10^6$.
• $1 \le a_i \le n - 1$.

It is guaranteed that there exists at least one subtask where the minimum value of the number of times operation 1 is used is $0$.

Translated by ChatGPT 5