Educational Codeforces Round 43(Rated for Div. 2) D. Degree set(욕심 귀속 구조)

D. Degree Set

Stetement

    You are given a sequence of n positive integers d1, d2, ..., dn(d1 < d2 < ... < dn) 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 dn + 1 d n   +   1 vertices;     there are no self-loops;     there are no multiple edges;     there are no more than 106 10 6 edges;     its degree set is equal to d.     Vertices should be numbered 1 through dn + 1 d n   +   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) 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) 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 ≤ 106) 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 106 10 6 edges.     Each of the next m lines should contain two integers vi v i and ui u i (1 ≤ vi, ui ≤ dn + 1) ( 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

제목

n개의 서로 다른 수의 도수 집합을 보여 줍니다. 그림을 만들어서 이 그림은 dn+1dn+1개의 점을 만족시키고 중변자환이 없고 10610개의 6개를 넘지 않으며 이 그림의 모든 점의 도수 insert가 하나의 set에 들어간 후에 입력한 집합과 같습니다.

사고방식 & 분석

먼저 확실한 것은 도수가 d[n]인 점은 틀림없이 다른 모든 점과 연결되어 있다는 것이다. 그러면 우리는 도수가 d[1]인 점의 모든 변은 도수가 d[n]인 점과 연결된 변이라고 가정한다. 그래서 우리는 d[1]개의 도수가 d[n]인 점이 생겼다. 이때 약간의 도수가 모두 d[1]를 차지하는 셈이다.그러면 우리는 d[2]~d[n-1]를 모두 d[1]에서 빼서 그를 하위 문제로 전환시켰다. 그러나 이 하위 문제의 요구 포인트는 바로 현재의 최대 도수+1, 즉 d[n-1]-d[1]+1이다.우리는 우리가 현재 구성한 이 그림이 d[1]개의 도수가 가장 큰 점을 제외하고 d[n]-d[1]+1개의 점이 남았다는 것을 안다. 그러면 우리는 d[n]-d[n-1]개의 도수가 d[1]인 점을 찾으면 된다.나머지는 모두 귀속되고, 경계는 점이 없을 때return, 또는 하나의 도수만 있을 때 완전도를 연결한다.

Code

#pragma GCC optimize(3)
#include
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
int n,d[305],cnt,u[1000006],v[1000006];
inline void solve(int l,int r,int vl,int vr) {
    if(l>r)
        return;
    if(l==r) {
        for(int i=vr;i>vl;--i)
            for(int j=vl;jreturn;
    } 
    int w=d[l];
    for(int i=vr;i>vr-w;--i)
        for(int j=vl;jint nxtl=vl+d[r]-d[r-1],nxtr=vr-d[l];
    for(int i=r;i>=l;--i)
        d[i]-=d[l];
    solve(l+1,r-1,nxtl,nxtr);
}
int main() {
    read(n);
    for(int i=1;i<=n;i++)
        read(d[i]);
    solve(1,n,1,d[n]+1);
    writeln(cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d %d
",u[i],v[i]);
}