题目描述

長さ $N$ の数列 $D_1,\ D_2,\ ...,\ D_N$ が与えられます。 $D_i$ の値はすべて異なります。 以下の条件を満たす $N$ 頂点の木は存在するでしょうか？

• 各頂点には $1,2,...,\ N$ の番号が付けられている
• 各辺には $1,2,...,\ N-1$ の番号が付けられていて、$i$ 番目の辺は頂点 $u_i$ と $v_i$ をつないでいる
• 各頂点 $i$ に対して、$i$ から他の頂点までの距離の和は $D_i$ である。ただし、各辺の長さは $1$ であるものとする。

条件を満たす木が存在する場合、$1$ つ構築してください。

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $D_1$ $D_2$ $:$ $D_N$

输出格式

条件を満たす $N$ 頂点の木が存在しない場合、-1 と出力してください。

条件を満たす $N$ 頂点の木が存在する場合、$N-1$ 行出力してください。 $i$ 行目には $u_i,v_i$ を空白区切りで出力してください。 複数の木が条件を満たす場合、どれを出力しても構いません。

题目大意

• 给出 $N$ 个互不相同的数 $D_i$，表示树上的节点 $i$ 到其他所有点的距离和。
• 请判断是否存在这样一棵树，其中每条边的长度均为 $1$。若存在请输出一种方案，否则输出 -1。
• $1 \leq N \leq 10^5$，$1 \leq D_i \leq 10^{12}$。

7
10
15
13
18
11
14
19

1 2
1 3
1 5
3 4
5 6
6 7

2
1
2

-1

15
57
62
47
45
42
74
90
75
54
50
66
63
77
87
51

1 10
1 11
2 8
2 15
3 5
3 9
4 5
4 10
5 15
6 12
6 14
7 13
9 12
11 13

提示

制約

• $2\ \leq\ N\ \leq\ 100000$
• $1\ \leq\ D_i\ \leq\ 10^{12}$
• $D_i$ はすべて異なる

Sample Explanation 1

次のような木が条件を満たします。