配点 : $900$ 点

問題文

長さ $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$ つ構築してください。

制約

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

入力

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

$N$

$D_1$

$D_2$

$:$

$D_N$

出力

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

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

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