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: interview

Starter code:

Solutions:
# python3


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


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
        #print(verticesCount)
        for i in range(1,verticesCount + 1):
            for j in range(i + 1,verticesCount + 1):
                edges.append([i,j])
        #print(edges)
        return edges , verticesCount
    
    newDegreeSet = []
    for i in range(1,n - 1):
        newDegreeSet.append(DegreSet[i ]- DegreSet[0])
    #print(newDegreeSet)    
    prevSolveDegreeSet = SolveDegreeSet(newDegreeSet, n - 2)

    verticesCount = prevSolveDegreeSet[1]
    edges = prevSolveDegreeSet[0]
    #print(edges)
    
    #print(verticesCount)
    
    verticesCount += (DegreSet[n-1] - DegreSet[n-2])
    #print(verticesCount)
    for i in range(0, DegreSet[0]):
        verticesCount += 1
        for j in range(1, verticesCount):
             edges.append([j, verticesCount])
    #print (edges)
    #print(verticesCount)
    return edges, verticesCount

n, = readline()
d = readline()

par = list(SolveDegreeSet(d, n))
edges = par[0]
#print( edges)
print(len(edges))
print("\n".join(map("{0[0]} {0[1]}".format, edges)))


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
        #print(verticesCount)
        for i in range(1,verticesCount + 1):
            for j in range(i + 1,verticesCount + 1):
                edges.append([i,j])
        #print(edges)
        return edges , verticesCount
    
    newDegreeSet = []
    for i in range(1,n - 1):
        newDegreeSet.append(DegreSet[i ]- DegreSet[0])
    #print(newDegreeSet)    
    prevSolveDegreeSet = SolveDegreeSet(newDegreeSet, n - 2)

    verticesCount = prevSolveDegreeSet[1]
    edges = prevSolveDegreeSet[0]
    #print(edges)
    
    #print(verticesCount)
    
    verticesCount += (DegreSet[n-1] - DegreSet[n-2])
    #print(verticesCount)
    for i in range(0, DegreSet[0]):
        verticesCount += 1
        for j in range(1, verticesCount):
             edges.append([j, verticesCount])
    #print (edges)
    #print(verticesCount)
    return edges, verticesCount

n, = readline()
d = readline()

par = list(SolveDegreeSet(d, n))
edges = par[0]
#print( edges)
print(len(edges))
print("\n".join(map("{0[0]} {0[1]}".format, edges)))