Restore Operation Sequence and DFS Order

You are given a rooted tree with \(n\) nodes (numbered from 1 to \(n\)) where node 1 is the root. Each node \(i\) has an initial weight \(w_i\). It is guaranteed that for any two nodes at the same depth, the number of children is identical. You are allowed to perform the following operation arbitrarily many times (each edge can be chosen at most once):

Choose an edge connecting two nodes \(u\) and \(v\), where \(u\) is the child of \(v\) (i.e. \(\text{depth}(u)>\text{depth}(v)\)). Then update \(w_u\) by adding \(w_v\) to it, that is, \(w_u \leftarrow w_u + w_v\).

After performing some operations, a DFS traversal of the tree is carried out. The weights of the nodes in the order they are visited are recorded into a sequence \(c\), where \(c_i\) is the weight of the node visited at the \(i\)-th position. Unfortunately, the specific sequence of operations and the DFS order used have been forgotten.

Your task is to restore any valid DFS order and a corresponding operation sequence (possibly empty) such that when applied to a tree with the given properties, the final weights in the DFS order equal the provided sequence \(c\). Note that if you choose to perform no operations, then the DFS order should correspond to the initial weights (i.e. \(w_i=c_i\) for the DFS order you output).

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of nodes in the tree.
• The second line contains \(n\) space-separated integers \(c_1, c_2, \ldots, c_n\), representing the recorded final weights of the nodes in some DFS order.

outputFormat

Output two parts:

• In the first line, output a permutation of \(1, 2, \ldots, n\) representing a DFS order of the tree.
• In the second line, output an integer \(m\) which denotes the number of operations performed.
• Then output \(m\) lines, each containing two integers \(u\) and \(v\) indicating that the operation on the edge connecting \(u\) (child) and \(v\) (parent) was performed, i.e. \(w_u\) was updated by adding \(w_v\).

If no operations are performed, simply output 0 in the second line.

sample

3
1 2 3

1 2 3
0