Degree Set

2000ms

262144K

Description:

You are given a sequence of n positive integers d₁, d₂, ..., d_n (d₁ < d₂ < ... < 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⁶ 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⁶ 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₁, d₂, ..., d_n (1 ≤ d_i ≤ 1000, d₁ < d₂ < ... < d_n) — the degree set.

Output:

In the first line print one integer m (1 ≤ m ≤ 10⁶) — 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⁶ 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.

Sample Input:

3
2 3 4

Sample Output:

Sample Input:

3
1 2 3

Sample Output:

Informação

Provedor Codeforces

Código CF976D