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

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
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  int d[1010];
  cin >> n;
  for (int i = 0; i < n; i++) cin >> d[i];
  vector<vector<int> > G(d[n - 1] + 1);
  int l = 0, m = 0;
  for (int i = 0, j = n - 1; i <= j; i++, j--) {
    for (int k = 0; k < d[i]; k++)
      for (int t = l; t <= l + d[j]; t++)
        if (t > k + l) {
          m++;
          G[t].push_back(k + l);
          G[k + l].push_back(t);
        }
    l += d[i] + 1;
    for (int k = j; k >= i; k--) d[k] -= d[i];
  }
  cout << m << endl;
  for (int i = 0; i < G.size(); i++)
    for (int j = 0; j < G[i].size(); j++)
      if (i < G[i][j]) cout << i + 1 << ' ' << G[i][j] + 1 << endl;
  return 0;
}
