Educational Codeforces Round 43 (Rated for Div. 2) D. Degree Set

 

D. Degree Set

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence of n positive integers d1, d2, ..., dn (d1 < d2 < ... < dn). Your task is to construct an undirected graph such that:

• there are exactly dn + 1 vertices;
• there are no self-loops;
• there are no multiple edges;
• there are no more than 106 edges;
• its degree set is equal to d.

Vertices should be numbered 1 through (dn + 1).

Degree sequence is an array a with length equal to the number of vertices in a graph such that ai 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 106 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 d1, d2, ..., dn (1 ≤ di ≤ 1000, d1 < d2 < ... < dn) — the degree set.

Output

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

Each of the next m lines should contain two integers vi and ui (1 ≤ vi, ui ≤ dn + 1) — the description of the i-th edge.

Examples

input

Copy

3
2 3 4

output

Copy

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

input

Copy

3
1 2 3

output

Copy

4
1 2
1 3
1 4
2 3

题意:构造一个d[n]+1个节点的图，要求度数包含在{d[1]...d[n]}之中，且至少出现一次。

原理:

证明:

#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define XINF INT_MAX
#define INF 0x3F3F3F3F
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
#define RIT reverse_iterator
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
typedef tree<PII, null_type, greater<PII>, rb_tree_tag, tree_order_statistics_node_update > rb_tree_set;
typedef tree<PII, PII, greater<PII>, rb_tree_tag, tree_order_statistics_node_update > rb_tree;
#define PQ std::priority_queue
#define HEAP __gnu_pbds::priority_queue
#define X first
#define Y second
#define lson(X) ((X)<<1)
#define rson(X) ((X)<<1|1)
#define EPS 10e-6
#define pi acos(-1)
#define N 1000
int d[N], in[N];
VII G;
int n;
int s, t;
void solve(int n, int d[], int s)
{
    REP(i, d[0]) {
        for(int j = s; j < t; ++j)
            G.PB(MP(j, t));
        t--;
    }
    if(n > 2) {
        REP2(i, 1, n-1) {
            d[i] = d[i]-d[0];
        }
        solve(n-2, d+1, t-d[n-2]);
    }
}
int main()
{
    scanf("%d", &n);
    REP(i, n)
        scanf("%d",&d[i]);
    s = 1, t = d[n-1]+1;
    solve(n, d, s);
    printf("%d\n",G.size());
    for(auto p : G) {
        printf("%d %d\n", p.X, p.Y);
    }
    return 0;
}