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-----
7
10
15
13
18
11
14
19

-----Sample Output-----
1 2
1 3
1 5
3 4
5 6
6 7

The tree shown below satisfies the conditions.

Difficulty: competition

Starter code:

Solutions:
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)

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()

n,*d = map(int,open(0).read().split())
z = {j:i for i,j in enumerate(d)}
*s, = sorted(d)
P = [-1]*n
S = {i:1 for i in d}
D = {i:0 for i in d}
ok = 1
for v in s[n-1:0:-1]:
    p = v-n+2*S[v]
    if p >= v: ok = 0
    if p in z:
        S[p] += S[v]
        D[p] += D[v]+S[v]
        P[z[v]] = z[p]
    else: ok = 0
if ok and D[s[0]]==s[0]:
    for i,pi in enumerate(P):
        if pi != -1: print(i+1,pi+1)
else: print(-1)

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)
	return
#print(d)
child = [1 for _ in range(n)]
#print(gap)
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])
	#print(i, x, n - 2+child[i], b)
	if d[b] != x - n + 2*child[i] or n <= 2*child[i]:
		print(-1)
		return
	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):
	nonlocal 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)

# -*- coding: utf-8 -*-
""" outputの時間比較 """
from sys import stdin, stdout
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list([int(x)-1 for x in 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())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()
def print_list(s):
    stdout.write(' '.join(list(map(str, s))) + '\n')
    # stdout.flush()
def print_single(s):
    stdout.write(str(s) + '\n')
    # stdout.flush()


# N = _i()
# D_list = np.array([_i() for _ in range(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)

# 解説を参考に実装
# Dのスコアが大きい方から小さい方へ伸びる有向エッジとみなす
# valueはノードから出ている有向エッジを切った場合の部分木の大きさ
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))
        return
    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]

# 1番目のノードについてチェック
if cost[0][0] != sorted_D[0]:
    print((-1))
    return
else:
    for a in ans:
        # print(a[0], a[1])
        print_list(a)


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

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

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 list(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))
        return

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


#!/usr/bin/env python3
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)


def __starting_point():
    main()


__starting_point()

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)
        return
    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)

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)
        return
    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)

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)

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

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

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 list(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))
        return

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


n,*d = map(int,open(0).read().split())
zd = {di:i for i,di in enumerate(d)}
*sd, = sorted(d)
parent = [-1]*n
size = {i:1 for i in d}
dist = {i:0 for i in d}
ok = 1
for v in sd[n-1:0:-1]:
    p = v - n + 2*size[v]
    if p >= v:
        ok = 0
        break
    if p in zd:
        size[p] += size[v]
        dist[p] += dist[v]+size[v]
        parent[zd[v]] = zd[p]
    else:
        ok = 0
        break
if dist[sd[0]] != sd[0]: ok = 0
if ok:
    for i,pi in enumerate(parent):
        if pi != -1: print(i+1,pi+1)
else:
    print(-1)

def solve(n, ddd):
    dsd = {d: i for i, d in enumerate(ddd)}
    child_cnt = [1] * n
    child_dist = [0] * n
    buf = []
    srt = sorted(list(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)))



def solve():
    # N = int(raw_input())
    # D = [int(raw_input()) for i in range(N)]
    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}
    # child = [[] for i in range(N)]
    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 list(d_to_i.keys()):
            node_par = d_to_i[valD_par]
            # child[node].append(node_par) ##
            # child[node_par].append(node)
            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
    # check if Di satisfied or not
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print ('-1')
        return
    # for i in range(N):
    #     for j in child[i]:
    #         print str(i + 1) + ' ' + str(j + 1)
    for i,j in ans:
        print((str(i) + ' ' + str(j)))

def __starting_point():
    solve()

__starting_point()

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)