Productive Meeting

题意翻译

## 题目描述 有 $n$ 个人被邀请参加一个即将召开重要会议。在会议中，任意两个人可以社交，相同的两个人可以社交任意次。 $n$ 个人中，每个人都有一个社交能力值，其中第 $i$ 个人的社交能力值是一个非负整数 $a_i$，它表示这个人可以与另一个人社交的次数。 在一个会议中，产生的社交次数越多，这次会议就会被认为越有效。具体地，一个会议的有效程度为这次会议进行时产生的社交次数。 给你序列 $a$，求出一次会议的最大有效程度，要求给出任意一种可以产生这个最大有效程度的方案。 ## 输入格式 多组数据。 第一行一个数 $t$ ，表示该测试点包含的测试样例数目。 接下来 $2t$ 行，描述了每一个测试用例。 每一组测试用例由两行组成： 1. 一个整数 $n$ ，表示参加这次会议的人数。 2. $n$ 个非负整数，表示序列 $a$，意义如题目描述中所述。 ## 输出格式 对于每一组测试用例： 先输出一行一个数，表示这次会议的最大有效程度 $p$。 然后是 $p$ 行，每一行包含两个整数 $i,j$ ，表示在你的方案中，编号为 $i$ 的人和编号为 $j$ 的人进行了一次社交。 ## 数据范围 $1\leq t\leq 10^3,2\leq n\leq 2\times 10^5$。 另外，保证对于所有测试样例中的 $n,a_i$，其和不超过 $2\times 10^5$。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

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