题目描述

给定一个长度为 $N$ 的数列 $D_1, D_2, \ldots, D_N$。所有 $D_i$ 的值都互不相同。请问是否存在一个具有 $N$ 个顶点的树满足以下条件？

• 每个顶点都标有 $1, 2, \ldots, N$ 的编号
• 每条边都标有 $1, 2, \ldots, N-1$ 的编号，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$
• 对于每个顶点 $i$，从 $i$ 到其他所有顶点的距离之和为 $D_i$。这里，每条边的长度都视为 $1$。

如果存在满足条件的树，请构造出其中一个。

输入格式

输入以以下格式通过标准输入给出。

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

输出格式

如果不存在满足条件的树，输出 -1。

如果存在满足条件的树，输出 $N-1$ 行。第 $i$ 行输出 $u_i, v_i$，以空格分隔。如果存在多个满足条件的树，输出其中任何一个即可。

输入输出样例 #1

输入 #1

7
10
15
13
18
11
14
19

输出 #1

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

输入输出样例 #2

输入 #2

2
1
2

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

数据范围

• $2\ \leq\ N\ \leq\ 100000$
• $1\ \leq\ D_i\ \leq\ 10^{12}$
• $D_i$ 互不相同

样例解释 1

存在如下满足条件的树：