分数: 900 点
问题陈述
给你一个序列 D_1, D_2, ..., D_N 长度 N. 的值 D_i 都是不同的。 树是否具有 N 满足以下条件的顶点存在吗?
- 顶点已编号 1,2,..., N.
- 边缘已编号 1,2,..., N-1和边缘 i 连接顶点 u_i 和 v_i.
- 对于每个顶点 i,距离的总和 i 到其他顶点是 D_i,假设每条边的长度为 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 之间有一个空格。 如果有多棵树满足条件,则任何这样的树都将被接受。
样本输入 1
7 10 15 13 18 11 14 19
示例输出 1
1 2 1 3 1 5 3 4 5 6 6 7
下面所示的树满足条件。

示例输入 2
2 1 2
示例输出 2
-1
示例输入 3
15 57 62 47 45 42 74 90 75 54 50 66 63 77 87 51
示例输出 3
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