You are given a sequence of n positive integers d_1, d_2, ..., d_{n} (d_1 < d_2 < ... < d_{n}). Your task is to construct an undirected graph such that:

  there are exactly d_{n} + 1 vertices;  there are no self-loops;  there are no multiple edges;  there are no more than 10^6 edges;  its degree set is equal to d. 

Vertices should be numbered 1 through (d_{n} + 1).

Degree sequence is an array a with length equal to the number of vertices in a graph such that a_{i} is the number of vertices adjacent to i-th vertex.

Degree set is a sorted in increasing order sequence of all distinct values from the degree sequence.

It is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than 10^6 edges.

Print the resulting graph.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 300) — the size of the degree set.

The second line contains n integers d_1, d_2, ..., d_{n} (1 ≤ d_{i} ≤ 1000, d_1 < d_2 < ... < d_{n}) — the degree set.


-----Output-----

In the first line print one integer m (1 ≤ m ≤ 10^6) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than 10^6 edges.

Each of the next m lines should contain two integers v_{i} and u_{i} (1 ≤ v_{i}, u_{i} ≤ d_{n} + 1) — the description of the i-th edge.


-----Examples-----
Input
3
2 3 4

Output
8
3 1
4 2
4 5
2 5
5 1
3 2
2 1
5 3

Input
3
1 2 3

Output
4
1 2
1 3
1 4
2 3

Difficulty: VERY_HARD
Tags: Graph algorithms

Implementation

Constructive algorithms

Starter code:

Solutions:
def readline():
	return list(map(int, input().split()))

def SolveDegreeSet(DegreSet, n):
	edges = []
	verticesCount = 0
	if n == 0:
		verticesCount = 1
		return (edges, verticesCount)
	if n == 1:
		verticesCount = DegreSet[0] + 1
		for i in range(1, verticesCount + 1):
			for j in range(i + 1, verticesCount + 1):
				edges.append([i, j])
		return (edges, verticesCount)
	newDegreeSet = []
	for i in range(1, n - 1):
		newDegreeSet.append(DegreSet[i] - DegreSet[0])
	prevSolveDegreeSet = SolveDegreeSet(newDegreeSet, n - 2)
	verticesCount = prevSolveDegreeSet[1]
	edges = prevSolveDegreeSet[0]
	verticesCount += DegreSet[n - 1] - DegreSet[n - 2]
	for i in range(0, DegreSet[0]):
		verticesCount += 1
		for j in range(1, verticesCount):
			edges.append([j, verticesCount])
	return (edges, verticesCount)
(n,) = readline()
d = readline()
par = list(SolveDegreeSet(d, n))
edges = par[0]
print(len(edges))
print('\n'.join(map('{0[0]} {0[1]}'.format, edges)))


def readline():
	return list(map(int, input().split()))

def solve(d):
	while d:
		dn = d.pop()
		if not d:
			for i in range(1, dn + 1):
				for j in range(i, dn + 1):
					yield (i, j + 1)
			return
		else:
			d1 = d.pop(0)
			for i in range(1, dn + 1):
				for j in range(max(dn - d1 + 1, i), dn + 1):
					yield (i, j + 1)
			d = [di - d1 for di in d]

def main():
	(n,) = readline()
	d = readline()
	assert len(d) == n
	edges = list(solve(d))
	print(len(edges))
	print('\n'.join(map('{0[0]} {0[1]}'.format, edges)))
main()


import sys
line = lambda : sys.stdin.buffer.readline()
n = int(line())
d = [0] + list(map(int, line().split()))
s = []
for i in range(1, n + 1):
	for u in range(d[i - 1] + 1, d[i] + 1):
		for v in range(u + 1, d[n - i + 1] + 2):
			s.append((u, v))
print(len(s))
for t in s:
	print(*t)


from sys import stdin
from sys import stdout
n = int(stdin.readline())
d = [0] + list(map(int, stdin.readline().split()))
e = []
for i in range(1, n + 1):
	for u in range(d[i - 1] + 1, d[i] + 1):
		for v in range(u + 1, d[n - i + 1] + 2):
			e.append([u, v])
stdout.write('{}\n'.format(len(e)))
for ei in e:
	stdout.write('{} {}\n'.format(ei[0], ei[1]))