Darius' Wisdom
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 1600
Tags: constructive algorithms, greedy, implementation, sortings

Darius the Great is constructing $$$n$$$ stone columns, each consisting of a base and between $$$0$$$, $$$1$$$, or $$$2$$$ inscription pieces stacked on top.

In each move, Darius can choose two columns $$$u$$$ and $$$v$$$ such that the difference in the number of inscriptions between these columns is exactly $$$1$$$, and transfer one inscription from the column with more inscriptions to the other one. It is guaranteed that at least one column contains exactly $$$1$$$ inscription.

Since beauty is the main pillar of historical buildings, Darius wants the columns to have ascending heights. To avoid excessive workers' efforts, he asks you to plan a sequence of at most $$$n$$$ moves to arrange the columns in non-decreasing order based on the number of inscriptions. Minimizing the number of moves is not required.

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

The first line of each test case contains an integer $$$n$$$ — the number of stone columns. ($$$1 \leq n \leq 2 \cdot 10^5$$$)

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i \in \{0,1,2\}$$$ represents the initial number of inscriptions in the $$$i$$$-th column. It is guaranteed that at least one column has exactly $$$1$$$ inscription.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output an integer $$$k$$$ — the number of moves used to sort the columns. ($$$0 \leq k \leq n$$$)

Then, output $$$k$$$ lines, each containing two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), representing the indices of the columns involved in the $$$i$$$-th move. During each move, it must hold that $$$|a_{u_i} - a_{v_i}| = 1$$$, and one inscription is transferred from the column with more inscriptions to the other.

It can be proven that a valid solution always exists under the given constraints.

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

Note:
Columns state in the first test case:

- Initial: $$$0, 2, 0, 1$$$
- After the first move: $$$0, 1, 0, 2$$$
- After the second move: $$$0, 0, 1, 2$$$

Columns state in the second test case:

- Initial: $$$1, 2, 0$$$
- After the first move: $$$0, 2, 1$$$
- After the second move: $$$0, 1, 2$$$

In the third test case, the column heights are already sorted in ascending order.

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

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

Editorial:
solution 1:
[spoiler]
We can assume $$$count(0) <= count(2)$$$ without loss of generality. (Why?)
[/spoiler]
[spoiler]
Now, the solution for the easy version applies here as well!
$$$$$$2 \cdot min(count(0), count(1)+count(2))+min(count(1), count(2)) = 2 \cdot count(0) + min(count(1), count(2)) $$$$$$ $$$$$$\le count(0) + max(count(1), count(2)) + min(count(1), count(2))=count(0)+count(1)+count(2)=n$$$$$$
[/spoiler]
Solution 2:
[spoiler]
We are allowed to perform $$$n$$$ moves. Assign one move to each index as its "specified cost."
[/spoiler]
[spoiler]
While there exists an index with a value of $$$0$$$ or $$$2$$$ that can be fixed using just one move, fix it using its specified cost.
[/spoiler]
[spoiler]
After ignoring fixed $$$0$$$'s, $$$2$$$'s, and all $$$1$$$'s except one, the remaining array looks like: $$$$$$ 2\ 2\ \dots\ 2\ (x\ \text{times})\ 1\ 0\ 0\ \dots\ 0\ (x\ \text{times}), $$$$$$ and we are allowed to use $$$2x + 1$$$ moves.
[/spoiler]
[spoiler]
First, swap the $$$1$$$ with a random element (denote it as $$$r$$$). Then, for $$$2x - 1$$$ moves, swap the index with the value $$$1$$$ with any index where the correct value must be, except $$$r$$$. Finally, swap $$$1$$$ and $$$r$$$.
[/spoiler]