It's Petya's birthday party and his friends have presented him a brand new "Electrician-n" construction set, which they are sure he will enjoy as he always does with weird puzzles they give him.

Construction set "Electrician-n" consists of 2n - 1 wires and 2n light bulbs. Each bulb has its own unique index that is an integer from 1 to 2n, while all wires look the same and are indistinguishable. In order to complete this construction set one has to use each of the wires to connect two distinct bulbs. We define a chain in a completed construction set as a sequence of distinct bulbs of length at least two, such that every two consecutive bulbs in this sequence are directly connected by a wire. Completed construction set configuration is said to be correct if a resulting network of bulbs and wires has a tree structure, i.e. any two distinct bulbs are the endpoints of some chain.

Petya was assembling different configurations for several days, and he noticed that sometimes some of the bulbs turn on. After a series of experiments he came up with a conclusion that bulbs indexed 2i and 2i - 1 turn on if the chain connecting them consists of exactly d_i wires. Moreover, the following important condition holds: the value of d_i is never greater than n.

Petya did his best but was not able to find a configuration that makes all bulbs to turn on, so he seeks your assistance. Please, find out a configuration that makes all bulbs shine. It is guaranteed that such configuration always exists.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the parameter of a construction set that defines the number of bulbs and the number of wires.

Next line contains n integers d_1, d_2, …, d_n (1 ≤ d_i ≤ n), where d_i stands for the number of wires the chain between bulbs 2i and 2i - 1 should consist of.

Output

Print 2n - 1 lines. The i-th of them should contain two distinct integers a_i and b_i (1 ≤ a_i, b_i ≤ 2n, a_i ≠ b_i) — indices of bulbs connected by a wire.

If there are several possible valid answer you can print any of them.

Examples

Input


3
2 2 2


Output


1 6
2 6
3 5
3 6
4 5


Input


4
2 2 2 1


Output


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


Input


6
2 2 2 2 2 2


Output


1 3
2 3
3 5
4 5
5 7
6 7
7 12
8 12
9 11
9 12
10 11


Input


2
1 1


Output


1 2
1 4
3 4

Note

<image> Answer for the first sample test.  <image> Answer for the second sample test.

Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

Sorting

Tree algorithms

Mathematics
Skill types: Sorting

Starter code:

Solutions:
n = int(input())
d = map(int, input().split())
d = [[2 * i + 1, di] for (i, di) in enumerate(d)]
d = sorted(d, key=lambda x: x[1], reverse=True)
edge = []
arr = [x[0] for x in d]
for (i, [x, d_]) in enumerate(d):
	if i + d_ - 1 == len(arr) - 1:
		arr.append(x + 1)
	edge.append([arr[i + d_ - 1], x + 1])
for (u, v) in zip(d[:-1], d[1:]):
	edge.append([u[0], v[0]])
ans = '\n'.join([str(u) + ' ' + str(v) for (u, v) in edge])
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
d = list(map(int, input().split()))
ANS = []

def pri(x, y):
	sys.stdout.write(str(x) + ' ' + str(y) + '\n')
D = [(x, i) for (i, x) in enumerate(d)]
D.sort(reverse=True)
CHAIN = [y * 2 + 1 for (_, y) in D]
for i in range(n - 1):
	pri(CHAIN[i], CHAIN[i + 1])
for i in range(n):
	(k, x) = D[i]
	use = CHAIN[i + k - 1]
	pri(use, x * 2 + 2)
	if use == CHAIN[-1]:
		CHAIN.append(x * 2 + 2)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
stored = [[10000000000, 0]]
gaped = [0]
for i in range(n):
	stored.append([a[i], 2 * i + 1])
stored.sort(reverse=True)
for i in range(1, n):
	gaped.append(stored[i][1])
	print(stored[i][1], stored[i + 1][1])
gaped.append(stored[-1][1])
l = n
for i in range(1, n + 1):
	if i + stored[i][0] == l + 1:
		print(gaped[-1], gaped[i] + 1)
		gaped.append(gaped[i] + 1)
		l += 1
	else:
		print(gaped[i + stored[i][0] - 1], gaped[i] + 1)


n = int(input())
d = [int(item) for item in input().split()]
ds = []
ans = []
for (i, item) in enumerate(d):
	ds.append((item, i))
ds.sort(reverse=True)
max_dist = ds[0][0]
max_idx = ds[0][1]
to_fill = max_dist - 1
ans = [[] for _ in range(max_dist + 1)]
ans[0].append(max_idx * 2 + 1)
ans[max_dist].append(max_idx * 2 + 2)
itr = 0
for (dist, idx) in ds[1:]:
	if to_fill == 0:
		break
	itr += 1
	odd = idx * 2 + 1
	ans[itr].append(odd)
	to_fill -= 1
to_fill = max_dist - 1
itr = 0
for (dist, idx) in ds[1:]:
	odd = idx * 2 + 1
	even = idx * 2 + 2
	if to_fill > 0:
		itr += 1
		if itr + dist == len(ans):
			ans.append([even])
		else:
			ans[itr + dist - 1].append(even)
	elif dist == 1:
		ans.append([odd])
		ans.append([even])
	else:
		ans[0].append(odd)
		ans[dist - 2].append(even)
	to_fill -= 1
prev_par = None
for line in ans:
	par = line[0]
	if prev_par is not None:
		print(prev_par, par)
	for item in line[1:]:
		print(par, item)
	prev_par = par


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	d = list(map(lambda xx: [int(xx), 0], input().split()))
	for i in range(n):
		d[i][1] = i + 1
	d.sort(key=lambda xx: xx[0], reverse=1)
	ls = [[2 * d[i][1] - 1] for i in range(n)]
	for i in range(n):
		x = i + d[i][0]
		if x >= len(ls):
			ls.append([2 * d[i][1]])
			continue
		ls[x - 1].append(2 * d[i][1])
	op = []
	for i in range(len(ls) - 1):
		op.append((ls[i][0], ls[i + 1][0]))
	for i in ls:
		for j in range(1, len(i)):
			op.append((i[0], i[j]))
	for i in op:
		print(*i)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
lis = list(map(int, input().split()))
li = sorted(range(len(lis)), key=lambda k: lis[k])
li = li[::-1]
ans = [2 * i + 1 for i in li]
for i in range(n - 1):
	print(ans[i], ans[i + 1])
for i in range(n):
	(k, x) = (lis[li[i]], li[i])
	u = ans[i + k - 1]
	print(u, x * 2 + 2)
	if u == ans[-1]:
		ans.append(x * 2 + 2)


n = int(input())
ds = map(int, input().split())
ds = [(d, id) for (id, d) in enumerate(ds)]
ds.sort()
(dMax, idMax) = ds.pop()
iCToI = {0: 2 * idMax, dMax: 2 * idMax + 1}
iCJTuples = [(dMax - 1, 2 * idMax + 1)]
id = 0
for iC in range(1, dMax):
	(d, id) = ds.pop()
	i = id * 2
	j = id * 2 + 1
	iCToI[iC] = i
	iCJTuples.append((iC - 1, i))
	newIC = iC + d
	if newIC not in iCToI:
		iCToI[newIC] = j
	iCJTuples.append((iC + d - 1, j))
ijTuples = []
for (iC, j) in iCJTuples:
	ijTuples.append((iCToI[iC], j))
while len(ds) > 0:
	(d, id) = ds.pop()
	i = id * 2
	j = id * 2 + 1
	if d == 1:
		ijTuples.append((i, j))
	else:
		ijTuples.append((iCToI[d - 2], j))
	ijTuples.append((i, iCToI[0]))
for (i, j) in ijTuples:
	print(i + 1, j + 1)


import sys
input = sys.stdin.readline
n = int(input())
l = input().split()
li = [(int(l[i]), i) for i in range(n)]
li.sort()
li.reverse()
l = [2 * li[0][1] + 1]
for i in range(n - 1):
	print(2 * li[i][1] + 1, 2 * li[i + 1][1] + 1)
	l.append(2 * li[i + 1][1] + 1)
for i in range(n):
	z = i + li[i][0] - 1
	print(l[z], 2 * li[i][1] + 2)
	if z == len(l) - 1:
		l.append(2 * li[i][1] + 2)


import sys
input = sys.stdin.readline
n = int(input())
d = [int(i) for i in input().split(' ')]
v = [2 * i + 1 for i in range(n)]
v.sort(key=lambda x: -d[x // 2])
for i in range(n - 1):
	print(v[i], v[i + 1])
currlen = len(v)
for i in range(n):
	if d[v[i] // 2] + i == currlen:
		v.append(v[i] + 1)
		currlen += 1
		print(v[-2], v[i] + 1)
	else:
		print(v[d[v[i] // 2] + i - 1], v[i] + 1)


n = int(input())
dists = list(map(int, input().split()))
dists = list(enumerate(dists))
dists.sort(key=lambda x: -x[1])
dist = [[2 * idx + 1] for (idx, _) in dists]
for (cur_idx, (idx, w)) in enumerate(dists):
	if cur_idx + w == len(dist):
		dist.append([2 * idx + 2])
	else:
		dist[cur_idx + w - 1].append(2 * idx + 2)
for idx in range(len(dist)):
	if idx != 0:
		print(dist[idx][0], dist[idx - 1][0])
	for i_idx in range(1, len(dist[idx])):
		print(dist[idx][i_idx], dist[idx][0])


n = int(input())
d = []
dfake = list(map(int, input().split(' ')))
for i in range(n):
	d.append((dfake[i], i + 1))
d.sort(reverse=True)
v = d[0][0] + 1
main = [0] * v
leaf = []
for i in range(v):
	leaf.append(set())
main[0] = d[0][1] * 2 - 1
main[-1] = d[0][1] * 2
vlen = v
for i in range(1, v - 1):
	temp = d[i][1] * 2 - 1
	main[i] = temp
	if i + d[i][0] == vlen:
		main.append(temp + 1)
		vlen += 1
		leaf.append(set())
	else:
		leaf[i + d[i][0] - 1].add(temp + 1)
for i in range(vlen - 1):
	m = main[i]
	print(m, main[i + 1])
	for j in leaf[i]:
		print(m, j)
m = main[0]
for i in range(v - 1, n):
	temp = d[i][1] * 2 - 1
	print(m, temp)
	local = d[i][0]
	if local > 1:
		print(main[local - 2], temp + 1)
	else:
		print(temp, temp + 1)


n = int(input())
ds = map(int, input().split())
ds = [(d, jd) for (jd, d) in enumerate(ds)]
ds.sort()
(d_max, jd_max) = ds.pop()
ic_to_i = {0: 2 * jd_max, d_max: 2 * jd_max + 1}
ic_j_tuples = [(d_max - 1, 2 * jd_max + 1)]
jd = 0
for ic in range(1, d_max):
	(d, jd) = ds.pop()
	i = jd * 2
	j = jd * 2 + 1
	ic_to_i[ic] = i
	ic_j_tuples.append((ic - 1, i))
	new_ic = ic + d
	if new_ic not in ic_to_i:
		ic_to_i[new_ic] = j
	ic_j_tuples.append((ic + d - 1, j))
i_j_tuples = []
for (ic, j) in ic_j_tuples:
	i_j_tuples.append((ic_to_i[ic], j))
while len(ds) > 0:
	(d, jd) = ds.pop()
	i = jd * 2
	j = jd * 2 + 1
	if d == 1:
		i_j_tuples.append((i, j))
	else:
		i_j_tuples.append((ic_to_i[d - 2], j))
	i_j_tuples.append((i, ic_to_i[0]))
for (i, j) in i_j_tuples:
	print(i + 1, j + 1)


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	d = list(map(int, input().split()))
	d = list(enumerate(d))
	d.sort(key=lambda x: x[1], reverse=True)
	edges = []

	def add_edge(a, b):
		edges.append((a, b))
	pos = 0
	cur_line = []
	pend = []
	flag = False
	for item in d:
		(_id, _d) = item
		if not flag and (not cur_line or cur_line[pos] >= 0):
			if cur_line:
				flag = True
			else:
				cur_line = [-1] * (_d + 1)
				pos = 0
		if flag:
			if _d == 1:
				add_edge(2 * _id, 2 * _id + 1)
				add_edge(cur_line[0], 2 * _id)
			else:
				add_edge(2 * _id, cur_line[1])
				add_edge(cur_line[_d - 1], 2 * _id + 1)
			continue
		cur_line[pos] = 2 * _id
		to = pos + _d
		while to >= len(cur_line):
			cur_line.append(-1)
		if cur_line[to] >= 0:
			if cur_line[to - 1] == -1:
				pend.append((2 * _id + 1, to - 1))
			else:
				add_edge(cur_line[to - 1], 2 * _id + 1)
		else:
			cur_line[to] = 2 * _id + 1
		pos += 1
	for (nod, to) in pend:
		add_edge(nod, cur_line[to])
	for i in range(1, len(cur_line)):
		add_edge(cur_line[i - 1], cur_line[i])
	assert len(edges) == 2 * n - 1
	for e in edges:
		print(f'{e[0] + 1} {e[1] + 1}')
main()


def solvea():
	n = int(input())
	d = int(input())
	e = 5 * int(input())
	best = 0
	for enr in range(n // e + 1):
		curr = e * enr
		curr += d * ((n - curr) // d)
		if curr <= n and curr > best:
			best = curr
	print(n - best)

def solveb():
	a = int(input())
	b = int(input())
	n = int(input())
	ans = 0
	for i in range(a + 1):
		for j in range(b + 1):
			if i + j == n:
				ans += 1
	print(ans)

def solvec():
	n = int(input())
	curr_bal = 0
	min_bal = 0
	for e in input():
		if e == '(':
			curr_bal += 1
		else:
			curr_bal -= 1
		if curr_bal < min_bal:
			min_bal = curr_bal
	if min_bal >= -1 and curr_bal == 0:
		print('Yes')
	else:
		print('No')

def solved():
	(n, m) = (int(x) for x in input().split())
	field = [input() for _ in range(n)]
	cell___is_possible = [[0 for j in range(m)] for i in range(n)]
	cell___is_possible[-1][-1] = True
	for j in reversed(range(m - 1)):
		cell___is_possible[-1][j] = cell___is_possible[-1][j + 1] and field[-1][j] == '.'
	for i in reversed(range(n - 1)):
		cell___is_possible[i][-1] = cell___is_possible[i + 1][-1] and field[i][-1] == '.'
	for i in reversed(range(n - 1)):
		for j in reversed(range(m - 1)):
			cell___is_possible[i][j] = field[i][j] == '.' and (cell___is_possible[i + 1][j] or cell___is_possible[i][j + 1])
	cell___is_reachable = [[0 for j in range(m)] for i in range(n)]
	cell___is_reachable[0][0] = True
	for j in range(1, m):
		cell___is_reachable[0][j] = cell___is_reachable[0][j - 1] and field[0][j] == '.'
	for i in range(1, n):
		cell___is_reachable[i][0] = cell___is_reachable[i - 1][0] and field[i][0] == '.'
	for i in range(1, n):
		for j in range(1, m):
			cell___is_reachable[i][j] = field[i][j] == '.' and (cell___is_reachable[i - 1][j] or cell___is_reachable[i][j - 1])
	dist___possibles_nr = [0] * (n + m - 1)
	for i in range(n):
		for j in range(m):
			dist___possibles_nr[i + j] += cell___is_possible[i][j] and cell___is_reachable[i][j]
	ans = min(dist___possibles_nr[1:-1])
	print(ans)

def solvee():
	n = int(input())
	dists = sorted([(int(x), 2 * i + 2) for (i, x) in enumerate(input().split())], reverse=True, key=lambda x: x[0])
	idx___node_id = [dists[i][1] for i in range(n)]
	edges = []
	for i in range(len(dists) - 1):
		edges.append((dists[i][1], dists[i + 1][1]))
	for (sorted_idx, (dist, even_id)) in enumerate(dists):
		odd_id = even_id - 1
		assert len(idx___node_id) - sorted_idx >= dist
		if len(idx___node_id) - sorted_idx == dist:
			edges.append((idx___node_id[-1], odd_id))
			idx___node_id.append(odd_id)
		elif sorted_idx + dist < len(idx___node_id):
			edges.append((idx___node_id[sorted_idx + dist - 1], odd_id))
	for edge in edges:
		print(*edge)
solvee()


n = int(input())
v = list(map(int, input().split()))
v = sorted([(v[i], i * 2 + 1) for i in range(n)], reverse=True)
print('\n'.join([str(v[i][1]) + ' ' + str(v[i + 1][1]) for i in range(n - 1)]))
r = [i[1] for i in v]
for i in range(n):
	print(v[i][1] + 1, r[v[i][0] + i - 1])
	if v[i][0] + i == len(r):
		r.append(v[i][1] + 1)