Productive Meeting
Contest: Codeforces Round 744 (Div. 3)
Difficulty rating: 1400
Tags: constructive algorithms, graphs, greedy

An important meeting is to be held and there are exactly $$$n$$$ people invited. At any moment, any two people can step back and talk in private. The same two people can talk several (as many as they want) times per meeting.

Each person has limited sociability. The sociability of the $$$i$$$-th person is a non-negative integer $$$a_i$$$. This means that after exactly $$$a_i$$$ talks this person leaves the meeting (and does not talk to anyone else anymore). If $$$a_i = 0$$$, the $$$i$$$-th person leaves the meeting immediately after it starts.

A meeting is considered most productive if the maximum possible number of talks took place during it.

You are given an array of sociability $$$a$$$, determine which people should talk to each other so that the total number of talks is as large as possible.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The next $$$2t$$$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) —the number of people in the meeting. The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) — the sociability parameters of all people.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that the sum of all $$$a_i$$$ (over all test cases and all $$$i$$$) does not exceed $$$2 \cdot 10^5$$$.

Output format:
Print $$$t$$$ answers to all test cases.

On the first line of each answer print the number $$$k$$$ — the maximum number of talks possible in a meeting.

On each of the next $$$k$$$ lines print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$ and $$$i \neq j$$$) — the numbers of people who will have another talk.

If there are several possible answers, you may print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
8
2
2 3
3
1 2 3
4
1 2 3 4
3
0 0 2
2
6 2
3
0 0 2
5
8 2 0 1 1
5
0 1 0 0 6

Example output:
2
1 2
1 2
3
1 3
2 3
2 3
5
1 3
2 4
2 4
3 4
3 4
0
2
1 2
1 2
0
4
1 2
1 5
1 4
1 2
1
5 2

Editorial:
For the first conversation let's choose two people $$$i$$$ and $$$j$$$ with maximal values of sociability. Note that after this conversation takes place, we move on to a similar problem, but in which $$$a_i$$$ and $$$a_j$$$ are decreased by $$$1$$$. After decreasing $$$a_i$$$ and $$$a_j$$$ by $$$1$$$, we repeat the choice of the two people with the maximum values of sociability. Let us repeat such iterations while at least two people with positive sociability parameters remain.
Let us prove that this solution leads to the optimal answer. Let's denote the sum $$$\sum\limits_{i = 1}^n a_i$$$ by $$$S$$$ and consider two fundamentally different cases:
1. The maximal element $$$a$$$ is greater than or equal to the sum of all remaining elements. That is, there exists $$$i$$$ such that $$$a_i \ge \sum\limits_{i \neq j} a_j = S - a_i$$$. In this case, note that the $$$i$$$-th person can not possibly have more than $$$S - a_i$$$ conversations, because by that point all other people already reached their sociability limits and left the meeting. Thus, if $$$a_i \ge S - a_i$$$, the answer cannot be more than $$$(S - a_i) + \sum\limits_{j \neq i} a_j = 2 \cdot (S - a_i)$$$. Note that this estimation is accurate since an example exists in which $$$i$$$-th person talks to all other people as many times as possible (that is, $$$a_j$$$ times with $$$j$$$-th person for all $$$j$$$). And the algorithm described above will just choose the $$$i$$$th person as one of the participants of a conversation every time, because for every conversation both $$$a_i$$$ and $$$\sum\limits_{j \neq i} a_j$$$ decrease by exactly $$$1$$$, so the inequality holds and it follows that $$$$$$\forall k \neq i:\, a_i \ge \sum\limits_{j \neq i} a_j \ge a_k\text{.}$$$$$$
2. Otherwise, we can prove that the maximum number of conversations is always $$$\left\lfloor\frac{S}{2}\right\rfloor$$$. Obviously, it is impossible to get more than this number, since each conversation requires exactly two units of sociability (one from two people), while a larger answer would mean that $$$$$$S = \sum\limits_{i = 1}^n a_i \ge 2 \cdot \left(\left\lfloor\frac{S}{2}\right\rfloor + 1\right) > S\text{,}$$$$$$ which is obviously wrong. Let us prove that this answer is achieved by the described algorithm. Let's look at the last conversation held. If there are at least two more people left in the meeting after it, we can hold another conversation, which means there is a more optimal answer. If there are zero people left in the meeting, then an estimate of $$$\frac{S}{2}$$$ of conversations has been achieved. And if there is one person with a remaining sociability $$$= 1$$$, then an estimate of $$$\frac{S - 1}{2}$$$ of conversations has been achieved. If there is exactly one remaining person $$$i$$$ with a sociability residual $$$> 1$$$, then we can guarantee that this person has participated in all previous conversations. Indeed, let's look at the last conversation — it was held between two people with the maximum parameters of the remaining sociability. But the $$$i$$$-th person has at least $$$2$$$ sociability remaining, so it couldn't have been the other two people with residuals of $$$1$$$ who left right after that. Thus, analyzing all conversations in reverse order, we can prove that at any time $$$a_i > \sum\limits_{j \neq i} a_j$$$, which means that it is in fact the case considered above.
We have proven that the described greedy algorithm works. This algorithm can be implemented by using any balanced search tree, such as std::set. By storing pairs of elements $$$(a_i, i)$$$ in it, we could for $$$\mathcal{O}(\log n)$$$ each time choose the next two people to talk to and update the sociability values.
The time complexity is $$$\mathcal{O}(S \log n)$$$.