← 返回题目列表

AtCoder · arc103_d

F. 距离总和

中文机器翻译题面 查看原题

分数: 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