Problem:
 Score : 900 points    Problem Statement You are given a sequence D_1, D_2, ..., D_N of length N . The values of D_i are all distinct. Does a tree with N vertices that satisfies the following conditions exist?   The vertices are numbered 1,2,..., N .  The edges are numbered 1,2,..., N-1 , and Edge i connects Vertex u_i and v_i .  For each vertex i , the sum of the distances from i to the other vertices is D_i , assuming that the length of each edge is 1 .   If such a tree exists, construct one such tree.      Constraints  2 \leq N \leq 100000  1 \leq D_i \leq 10^{12}  D_i are all distinct.         Input Input is given from Standard Input in the following format:  N  D_1  D_2  :  D_N       Output If a tree with n vertices that satisfies the conditions does not exist, print -1 .  If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i -th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.        Sample Input 1 7
10
15
13
18
11
14
19      Sample Output 1 1 2
1 3
1 5
3 4
5 6
6 7  The tree shown below satisfies the conditions.        Sample Input 2 2
1
2      Sample Output 2 -1       Sample Input 3 15
57
62
47
45
42
74
90
75
54
50
66
63
77
87
51      Sample Output 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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n = int(input())
d = [int(input()) for _ in range(n)]
r = {v: i for i, v in enumerate(d)}
sz = [1] * n
dsorted = sorted(((di, i) for i, di in enumerate(d)), reverse=True)
ans = []
to = [[] for _ in range(n)]
for di, i in dsorted[:n-1]:
    nd = di + (sz[i] - 1) - (n - 2 - (sz[i] - 1))
    if not nd in r:
        print(-1)
        exit()
    p = r[nd]
    to[p].append(i)
    sz[p] += sz[i]
    ans.append((i+1, p+1))

root = dsorted[-1][1]
def dfs(u, cur=0):
    rv = cur
    for v in to[u]:
        rv += dfs(v, cur + 1)
    return rv

if dfs(root) != d[root]:
    print(-1)
    exit()

for u, v in ans:
    print(u, v)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc103/tasks/arc103_d

面白そう！
とっかかりはどのへんだろうか

偶奇あたりから考えてみる？
まず、A→BとA←B　の距離は等しいので、Dの合計は絶対偶数になる
Dの和が奇数なら構築不可能

辺u,vを取り除いて,2つの部分木に分解する、各木の含む頂点数を x[u],x[v]とすると
D[u]+x[u] == D[v]+x[v]　となる (x[u] + x[v] == N)

最大のDについて考えてみよう
最大のDから繋がってる点を根とした部分木は少なくとも半分の数の要素を含む
なので、Dmaxは2つ以上辺を持っていてはいけない→Dmaxは葉

Dmaxを置くと、それとつながる要素のdは1意に定まる
残り(unused)の頂点の内、最大のを考える。
こいつももう葉になるしかない
1意に定まりんぐ

ん～？
こんな感じで大を小につけていけば構築完了するんじゃね？
小-大-小　となることはない(小の成分は半分以上の点を含むため)　なのでおｋそう！

D[u] > D[v]のとき
D[v] = D[u] + x[u] - x[v]
x[v] = N-x[u]なので
D[v] = D[u] + 2*x[u] - N

だめな理由がわからないが…
可能性1: 大が2つ以上の小に繋がってる場合がある(可能を-1にしてる)
可能性2: 実は構築したやつが条件を満たしてない(-1を可能にしてる)
→どっちもそんなこと無さそうなのに…

====テストケースを見たら2っぽさそう====
可能性2の方をつぶそう
→連結じゃない？自分より小さいdにすべて繋いでるんだからそんなことないだろ

じゃあ場合によってはxが違う？
→どんな場合よ？
→うーん？　最後に一応チェック機構入れるか
→つまりジャッジを書く

簡易的に、xに問題が生じてそうなとき(根がNになってないとき)は-1にするようにしてみた
→xの数がちゃんと計算されていないわけではない？？

===kmjp氏のぶろぐ===
検算が必要？？なんで？
dの条件は必要条件であって十分条件ではないからか！
→むずいよ…
dの間に成り立つべき関係を書いただけで、d全部がずれてる可能性があると…

→つまり1頂点の付いて成立すればいいので、根のdを調べてあげればいいか
"""

import sys
N = int(input())

Dz = 0
Di = []
d_to_ind = {}

for i in range(N):
    d = int(input())
    if i == 0:
        Dz = d
    Di.append([d,i])
    d_to_ind[d] = i

Di.sort()
Di.reverse()

x = [1] * N
ans = []
lis = [ [] for i in range(N) ]

for lp in range(N-1):

    nowd,nowi = Di[lp]

    nexd = nowd + 2*x[nowi] - N

    if nexd >= nowd:
        print (-1)
        sys.exit()

    if nexd not in d_to_ind:
        print (-1)
        sys.exit()

    nexi = d_to_ind[nexd]
    x[nexi] += x[nowi]
    ans.append([nowi+1,nexi+1])
    lis[nowi].append(nexi)
    lis[nexi].append(nowi)


from collections import deque
q = deque([0])
dis = [float("inf")] * N
dis[0] = 0
while len(q) > 0:
    now = q.popleft()
    for nex in lis[now]:
        if dis[nex] > dis[now]:
            dis[nex] = dis[now] + 1
            q.append(nex)

if sum(dis) != Dz:
    print (-1)
    sys.exit()

for i in range(N-1):

    print (ans[i][0] , ans[i][1])

Solution (Python):
n = int(input())
a = []
s = []

for i in range(n):
    x = int(input())
    a.append(x * n + i)
    s.append(1)

a.sort()
a.reverse()
a.append(-1)
Sum = 0

Have = True

result = []

for i in range(n - 1):
    l = 0
    r = n

    val = (a[i] // n) + s[i] + s[i] - n

    while (l < r):
        m = (l + r + 2) // 2

        if (a[m] >= val * n):
            l = m
        else:
            r = m - 1

    if((a[l] // n) != val):
        Have = False
        break

    s[l] += s[i]
    Sum  += s[i]
    result.append([a[i] % n,a[l] % n])

if (Sum != (a[n - 1] // n)):
    Have = False

if (Have == False):
    print("-1")
else:
    for e in result:
        print(e[0] + 1,end = " ")
        print(e[1] + 1)

Solution (Python):
def main():
    N = int(input())
    D = [int(input()) for i in range(N)]
    C = [1] * N
    T = [0] * N
    DI = {}
    for i in range(len(D)):
        DI[D[i]] = i
    D = sorted(D)
    P = [-1] * N
    while len(D) > 1:
        d = D.pop()
        i = DI[d]
        nd = d - N + C[i] * 2
        if nd in DI:
            ni = DI[nd]
        else:
            print(-1)
            return
        P[i] = ni
        C[ni] += C[i]
        T[ni] += T[i] + C[i]
    
    if D[0] == T[DI[D[0]]]:
        for i in range(N):
            if P[i] >= 0: print(i+1, P[i]+1)
    else:
        print(-1)

main()

Solution (Python):
import sys
from bisect import bisect_left
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)

n = int(input())
d = [[int(input()), i+1] for i in range(n)]
check = d[0][0]
d.sort()
ind = [x[1] for x in d]
d = [x[0] for x in d]
if n <= 3:
	print(-1)
	sys.exit()

child = [1 for _ in range(n)]

ans = []
adj = [[] for _ in range(n)]
for i in range(n-1, 0, -1):
	x = d[i]
	b = bisect_left(d, x - n + 2*child[i])
	
	if d[b] != x - n + 2*child[i] or n <= 2*child[i]:
		print(-1)
		sys.exit()
	else:
		child[b] += child[i]
		ans.append([ind[b], ind[i]])
		adj[ind[b]-1].append(ind[i]-1)
		adj[ind[i]-1].append(ind[b]-1)


res = 0
def dfs(x, p, dis):
	global res
	res += dis
	for v in adj[x]:
		if v == p:
			continue
		else:
			dfs(v, x, dis+1)
	return

dfs(0, -1, 0)
if res == check:
	for a in ans:
		print(*a)
else:
	print(-1)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
D = [None] + [int(input()) for _ in range(N)]

parent = [None] * (N+1)
size = [None] + [1] * N 
d_to_i = {d:i for i,d in enumerate(D)}
D_desc = sorted(D[1:],reverse=True)
D_subtree = [0] * (N+1)
edges = []

bl = True
for d in D_desc[:-1]:
    i = d_to_i[d]
    d_parent = d - N + 2*size[i]
    if d_parent not in d_to_i:
        bl = False
        break
    p = d_to_i[d_parent]
    edges.append('{} {}'.format(i,p))
    parent[i] = p
    size[p] += size[i]
    D_subtree[p] += D_subtree[i] + size[i]

root = d_to_i[D_desc[-1]]
bl &= (D_subtree[root] == D[root])

if bl:
    print('\n'.join(edges))
else:
    print(-1)

Solution (Python):
from collections import Counter
import sys
def muri():
    print(-1)
    sys.exit()
N = int(input())
D = [int(sys.stdin.readline()) for _ in range(N)]

Didx = list(range(1, N+1))
Didx.sort(key = lambda x: -D[x-1])
H = {d: i for i, d in enumerate(D, 1)}
H = Counter(H)
D = [0] + D
K = [1]*(N+1)
Ans = []
for vn in Didx[:-1]:
    p = H[D[vn] - (N - 2*K[vn])]
    if not p:
        muri()
    Ans.append((vn, p))
    K[p] += K[vn]
s = set()

Edge = [[] for _ in range(N+1)]
for a in Ans:
    x, y = a
    Edge[x].append(y)
    Edge[y].append(x)

dist = [10**9+7]*(N+1)
dist[0] = 0
dist[1] = 0
stack = [1]
visited = set([1])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in visited:
            visited.add(vf)
            dist[vf] = 1 + dist[vn]
            stack.append(vf)
if D[1] != sum(dist[1:]):
    muri()

for a in Ans:
    print(*a)

Solution (Python):

import sys

sys.setrecursionlimit(101010)

def dfs(v, adj_list, depth, visited):
    visited[v] = True
    x = depth
    for w in adj_list[v]:
        if not visited[w]:
            x += dfs(w, adj_list, depth + 1, visited)

    return x


def solve(n, d):

    if n < 7:
        print(-1)
        return

    d.sort()
    w = [1] * n
    edges = []
    adj_list = [[] for _ in range(n)]
    for j in range(n - 1, 0, -1):
        di, i = d[j]
        pdi = di - n + 2 * w[i]
        p = None
        lo, hi = 0, j
        while lo < hi:
            mid = (lo + hi) // 2
            xdi, xi = d[mid]
            if xdi == pdi:
                p = xi
                break
            elif xdi < pdi:
                lo = mid + 1
            else:
                hi = mid
        if p is None:
            print(-1)
            return
        u, v = i, p
        if v < u:
            u, v = v, u
        edges.append((u + 1, v + 1))
        adj_list[u].append(v)
        adj_list[v].append(u)
        w[p] += w[i]

    d0, r = d[0]
    visited = [False] * n
    x = dfs(r, adj_list, 0, visited)
    if x != d0:
        print(-1)
        return

    edges.sort()
    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))



def main():
    n = input()
    n = int(n)
    d = []
    for i in range(n):
        di = input()
        di = int(di)
        d.append((di, i))


    solve(n, d)


if __name__ == '__main__':
    main()

Solution (Python):

def solve():
    
    
    N = int(input())
    D = [int(input()) for i in range(N)]
    if sum(D) % 2 > 0:
        print ('-1')
        return
    Di = sorted([(di, i) for i, di in enumerate(D)], key = lambda x : x[0], reverse = True)
    d_to_i = {dd:i for dd, i in Di}
    
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    for valD, node in Di:
        valD_par = valD - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            
            
            ans.append((node_par + 1, node + 1))
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
            if n_child[node_par] == N:
                break
        else:
            print ('-1')
            return
    
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print ('-1')
        return
    
    
    
    for i,j in ans:
        print (str(i) + ' ' + str(j))

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)

Solution (Python):

""" outputの時間比較 """
from sys import stdin, stdout
import numpy as np



def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  
def print_list(s):
    stdout.write(' '.join(list(map(str, s))) + '\n')
    
def print_single(s):
    stdout.write(str(s) + '\n')
    




N = d_in()
D_list = np.array([d_in() for _ in range(N)])


idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)




nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]

for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]


if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        
        print_list(a)

Solution (Python):

""" インプットの時間比較 """
from sys import stdin
import numpy as np



def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  




N = d_in()
D_list = np.array([d_in() for _ in range(N)])


idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)




nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]

for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]


if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])

Solution (Python):

from sys import stdin
import numpy as np



def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
D_list = np.array([_i() for _ in range(N)])
idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)




nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]

for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]


if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])

Solution (Python):
n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)

Solution (Python):
N=int(input())
numlist=list(map(int,(input() for _ in range(N))))
numdict={y:x for x,y in enumerate(numlist)}
sorted_list=sorted(numdict.items(),reverse=True)

amount_of_child=[1]*N
sum_of_distance_of_child=[0]*N
branch_list=[]

for S,num in sorted_list:
  nS=S+2*amount_of_child[num]-N
  if nS in numdict:
    nextnum=numdict[nS]
    branch_list.append([num+1,nextnum+1])
    amount_of_child[nextnum]+=amount_of_child[num]
    sum_of_distance_of_child[nextnum]+=(sum_of_distance_of_child[num]+amount_of_child[num])
    if amount_of_child[nextnum]==N:
      break
  else:
    print (-1)
    exit()

if sorted_list[-1][0]==sum_of_distance_of_child[sorted_list[-1][1]]:
  for _ in range(N-1):
    x,y=branch_list.pop()
    print(x,y)
else:
  print (-1)
exit()

Solution (Python):
N=int(input())
numlist=list(map(int,(input() for _ in range(N))))
numdict={y:x for x,y in enumerate(numlist)}
sorted_list=sorted(numdict.items(),reverse=True)

nextS=lambda Snow,child : Snow+2*child-N

amount_of_child=[1]*N
sum_of_distance_of_child=[0]*N
branch_list=[]

for S,num in sorted_list:
  nS=nextS(S,amount_of_child[num])
  if nS in numdict:
    nextnum=numdict[nS]
    branch_list.append([num+1,nextnum+1])
    amount_of_child[nextnum]+=amount_of_child[num]
    sum_of_distance_of_child[nextnum]+=(sum_of_distance_of_child[num]+amount_of_child[num])
    if amount_of_child[nextnum]==N:
      break
  else:
    print (-1)
    exit()

if sorted_list[-1][0]==sum_of_distance_of_child[sorted_list[-1][1]]:
  for _ in range(N-1):
    x,y=branch_list.pop()
    print(x,y)
else:
  print (-1)
exit()

Solution (Python):
N=int(input())
numlist=[int(input()) for _ in range(N)]
numdict={y:x for x,y in enumerate(numlist)}
sorted_list=sorted(numdict.items(),reverse=True)

nextS=lambda Snow,child : Snow+2*child-N

amount_of_child=[1]*N
sum_of_distance_of_child=[0]*N
branch_list=[]

for S,num in sorted_list:
  nS=nextS(S,amount_of_child[num])
  if nS in numdict:
    nextnum=numdict[nS]
    branch_list.append([num+1,nextnum+1])
    amount_of_child[nextnum]+=amount_of_child[num]
    sum_of_distance_of_child[nextnum]+=(sum_of_distance_of_child[num]+amount_of_child[num])
    if amount_of_child[nextnum]==N:
      break
  else:
    print (-1)
    exit()

if sorted_list[-1][0]==sum_of_distance_of_child[sorted_list[-1][1]]:
  for _ in range(N-1):
    x,y=branch_list.pop()
    print(x,y)
else:
  print (-1)
exit()

Solution (Python):
def solve(n, ddd):
    dsd = {d: i for i, d in enumerate(ddd)}
    child_cnt = [1] * n
    child_dist = [0] * n
    buf = []
    srt = sorted(dsd.items(), reverse=True)
    for d, i in srt[:-1]:
        cc = child_cnt[i]
        pd = d - (n - cc * 2)
        if pd == d or pd not in dsd:
            return -1
        pi = dsd[pd]
        buf.append((pi + 1, i + 1))
        child_cnt[pi] += cc
        child_dist[pi] += child_dist[i] + cc

    md, mi = srt[-1]
    if md != child_dist[mi]:
        return -1
    return buf


n = int(input())
ddd = list(map(int, (input() for _ in range(n))))
res = solve(n, ddd)
if res == -1:
    print(-1)
else:
    print('\n'.join('{} {}'.format(*l) for l in res))

Solution (Python):
N = int(input())
src = [int(input()) for i in range(N)]
idx = {a:i for i,a in enumerate(src)}

size = [1] * N
ss = list(sorted(src))

es = []
gr = [[] for i in range(N)]
while len(ss) > 1:
    a = ss.pop()
    k = size[idx[a]]
    b = a + 2*k - N
    if b == a or b not in idx:
        print(-1)
        exit()
    size[idx[b]] += k
    ai,bi = idx[a],idx[b]
    es.append((ai,bi))
    gr[ai].append(bi)
    gr[bi].append(ai)

from collections import deque
dist = [N] * N
dist[idx[ss[0]]] = 0
q = deque([idx[ss[0]]])
while q:
    v = q.popleft()
    for to in gr[v]:
        if dist[to] < N: continue
        q.append(to)
        dist[to] = dist[v] + 1

if all(d<N for d in dist) and sum(dist) == ss[0]:
    for a,b in es:
        print(a+1, b+1)
else:
    print(-1)

Solution (Python):
N = int(input())
src = [int(input()) for i in range(N)]
idx = {a:i for i,a in enumerate(src)}

size = [1] * N
ss = list(sorted(src))

es = []
while len(ss) > 1:
    a = ss.pop()
    k = size[idx[a]]
    b = a + 2*k - N
    if b == a or b not in idx:
        print(-1)
        exit()
    size[idx[b]] += k
    es.append((idx[a],idx[b]))

gr = [[] for i in range(N)]
for a,b in es:
    gr[a].append(b)
    gr[b].append(a)

from collections import deque
dist = [N] * N
dist[idx[ss[0]]] = 0
q = deque([idx[ss[0]]])
while q:
    v = q.popleft()
    for to in gr[v]:
        if dist[to] < N: continue
        q.append(to)
        dist[to] = dist[v] + 1

if all(d<N for d in dist) and sum(dist) == ss[0]:
    for a,b in es:
        print(a+1, b+1)
else:
    print(-1)

Solution (Python):
from collections import defaultdict
N = int(input())
C = defaultdict(int)
for i in range(N):
  D = int(input())
  C[D] = i + 1
E = []
H = [1] * (N + 1)
DD = sorted([[k, v] for k, v in C.items()], reverse=True)
Adj = [[] for i in range(N)]
for D, n in DD[:-1]:
  try:
    p = C[D - N + 2 * H[n]]
    if n == p:
      raise Error
    E.append([n, p])
    Adj[n - 1].append(p - 1)
    Adj[p - 1].append(n - 1)
    H[p] += H[n]
  except:
    print(-1)
    break
else:
  dist = [N] * N
  dist[DD[-1][1] - 1] = 0
  Q = [DD[-1][1] - 1] + [N] * N
  tail = 1
  for i in range(N):
    s = Q[i]
    if s == N:
      print(-1)
      break
    for adj in Adj[s]:
      if dist[adj] == N:
        dist[adj] = dist[s] + 1
        Q[tail] = adj
        tail += 1
  else:
    if sum(dist) == DD[-1][0]:
      for e in E:
        print(e[0], e[1])
    else:
      print(-1)