<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

138. Games of Chess

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


N friends gathered in order to play chess, according to the following rules. In the first game, two of the N friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the N friends played, find a schedule for the games, so that the above rules are obeyed.


Input

The first line contains the number of friends N (2<=N<=100). The second line contains N integers, separated by blanks, representing the number of games each friend played. The first number represents the number of games played by the first friend, the second number represents the number of games played by the second friend and so on..


Output

The first line should contain the number of games played by all the friends (it will be an integer between 1 and 10 000, for every test case). Let's suppose this number is G. Then, G lines follow, each of them containing two integers, describing the games. The first line contains the numbers of the two friends who played the first game. The friend printed first is considered to be the winner. Each of the next G-1 lines contain the integers a and b, where a<>b and a or b is the winner of the previous game. The friend printed first on the line is considered to be the winner of the game.
It is guaranteed that for every test case there will be at least one possible scheduling of the games.


Sample Input

4
2 4 1 5
Sample Output

6
4 3
4 1
2 4
2 1
4 2
2 4
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

<|response|>
1. Abridged Problem Statement
You have N players, each of whom must appear in exactly a[i] games (as winner or loser). You need to arrange a sequence of G = (∑a[i])⁄2 chess games so that:
- In game 1, any two players meet.
- In each subsequent game, one of the players is the winner of the previous game.
- No game is drawn.
Output any valid sequence of G games (winner, loser) satisfying the above and the per-player appearance counts.

2. Key Observations
- The total number of games G = (∑a[i])⁄2 must be integer and it is guaranteed a solution exists.
- We need to build a chain of games: the “current champion” (winner of the last game) must play in the next game.
- If the champion has more than one game remaining, it’s safe to let him win again (we consume one of his required games but keep him champion).
- If the champion has exactly one game left, he cannot win (or he’d have zero games left but still need to hand off), so we force him to lose to someone else who still needs games, passing the champion role.
- Games where the champion wins can initially record only the winner, and we fill in losers later from the pool of players with remaining required games.

3. Full Solution Approach
1. Read N and array a[1..N]. Compute sum = ∑a[i], G = sum/2.
2. Sort the degrees a[] in descending order in place, and keep a permutation perm that records the original index of each sorted position. Position 0 is the initial “champion.”
3. Phase 1 (Decide winners & placeholders):
   - Initialize an empty list matches. Let pos = 0 (current champion position).
   - Repeat G times:
     a. If a[pos] > 1, record a match (winner = pos, loser = –1 placeholder), decrement a[pos].
     b. Else (a[pos] == 1), record match (winner = pos+1, loser = pos), decrement a[pos] and a[pos+1], then set pos = pos+1 (new champion).
4. Phase 2 (Assign actual losers):
   - Continue scanning from the current pos; whenever a match has loser == –1, advance pos until a[pos] > 0, set that match’s loser = pos, and decrement a[pos].
5. Output G, then for each match (w_idx, l_idx), print “perm[w_idx]+1 perm[l_idx]+1” on its own line.

This constructs a valid chain: in Phase 1 every next game involves the champion, and in Phase 2 we ensure every player reaches its required total appearances.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    /*
     * The games form a chain where the winner of each game plays the next, so
     * game g and game g+1 share exactly one player (the carried-over winner).
     * The total number of games is G = (sum of all game counts) / 2.
     *
     * Sort players by remaining game count descending (perm records original
     * indices). Build the winner column greedily: while the busiest player
     * still owes more than one game, make him the winner of the next game and
     * defer choosing his opponent; when he owes exactly one, he plays the next
     * player and we advance. We then fill each deferred opponent slot with the
     * next player that still has games left. Outputting (winner, loser) per
     * game with the winner first satisfies the "winner plays next" rule.
     */

    int sum_deg = accumulate(a.begin(), a.end(), 0);
    assert(sum_deg % 2 == 0);

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    sort(perm.begin(), perm.end(), [&](int i, int j) {
        return a[i] > a[j];
    });
    sort(a.rbegin(), a.rend());

    vector<pair<int, int>> matches;
    int pos = 0;
    for(int i = 0; i < sum_deg / 2; i++) {
        if(a[pos] == 1) {
            matches.emplace_back(pos + 1, pos);
            a[pos]--;
            a[pos + 1]--;
            pos++;
        } else {
            matches.emplace_back(pos, -1);
            a[pos]--;
        }
    }

    for(auto& match: matches) {
        if(match.second != -1) {
            continue;
        }
        while(a[pos] == 0) {
            pos++;
        }

        match.second = pos;
        a[pos]--;
    }

    cout << matches.size() << '\n';
    for(const auto& match: matches) {
        cout << perm[match.first] + 1 << ' ' << perm[match.second] + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys

def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    a = list(map(int, data[1:]))

    total = sum(a)
    G = total // 2

    # Sort players descending by required appearances
    perm = list(range(N))
    perm.sort(key=lambda i: -a[i])

    # b[k] = remaining appearances of player perm[k]
    b = [a[i] for i in perm]

    # matches: list of [winner_idx, loser_idx] where loser_idx=-1 means placeholder
    matches = []
    p = 0  # current champion position in b

    # Phase 1: decide winners and placeholders
    for _ in range(G):
        if b[p] > 1:
            # champion wins, postpone opponent
            matches.append([p, -1])
            b[p] -= 1
        else:
            # champion must lose to pass on token
            matches.append([p+1, p])
            b[p]   -= 1
            b[p+1] -= 1
            p += 1  # new champion

    # Phase 2: assign actual losers to placeholder matches
    q = 0
    for mv in matches:
        if mv[1] == -1:
            while b[q] == 0:
                q += 1
            mv[1] = q
            b[q] -= 1

    # Output, mapping back to original labels (1-based)
    out = [str(G)]
    for w, l in matches:
        out.append(f"{perm[w]+1} {perm[l]+1}")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```
