Bouncing Boomerangs
Contest: Codeforces Raif Round 1 (Div. 1 + Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, greedy, implementation

To improve the boomerang throwing skills of the animals, Zookeeper has set up an $$$n \times n$$$ grid with some targets, where each row and each column has at most $$$2$$$ targets each. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right.

For each column, Zookeeper will throw a boomerang from the bottom of the column (below the grid) upwards. When the boomerang hits any target, it will bounce off, make a $$$90$$$ degree turn to the right and fly off in a straight line in its new direction. The boomerang can hit multiple targets and does not stop until it leaves the grid.

In the above example, $$$n=6$$$ and the black crosses are the targets. The boomerang in column $$$1$$$ (blue arrows) bounces $$$2$$$ times while the boomerang in column $$$3$$$ (red arrows) bounces $$$3$$$ times.

The boomerang in column $$$i$$$ hits exactly $$$a_i$$$ targets before flying out of the grid. It is known that $$$a_i \leq 3$$$.

However, Zookeeper has lost the original positions of the targets. Thus, he asks you to construct a valid configuration of targets that matches the number of hits for each column, or tell him that no such configuration exists. If multiple valid configurations exist, you may print any of them.

Input format:
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(0 \leq a_i \leq 3)$$$.

Output format:
If no configuration of targets exist, print $$$-1$$$.

Otherwise, on the first line print a single integer $$$t$$$ $$$(0 \leq t \leq 2n)$$$: the number of targets in your configuration.

Then print $$$t$$$ lines with two spaced integers each per line. Each line should contain two integers $$$r$$$ and $$$c$$$ $$$(1 \leq r,c \leq n)$$$, where $$$r$$$ is the target's row and $$$c$$$ is the target's column. All targets should be different.

Every row and every column in your configuration should have at most two targets each.

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

Note:
For the first test, the answer configuration is the same as in the picture from the statement.

For the second test, the boomerang is not supposed to hit anything, so we can place $$$0$$$ targets.

For the third test, the following configuration of targets matches the number of hits, but is not allowed as row $$$3$$$ has $$$4$$$ targets.

It can be shown for this test case that no valid configuration of targets will result in the given number of target hits.

Example input:
6
2 0 3 0 1 1

Example output:
5
2 1
2 5
3 3
3 6
5 6

Example input:
1
0

Example output:
0

Editorial:
Clearly, columns with $$$a_j=0$$$ are completely empty and we can ignore them.
Let's first consider just columns with $$$1$$$s and $$$2$$$s. When a boomerang strikes its first target, it will change directions from upwards to rightwards. If $$$a_j=1$$$, the boomerang in column $$$j$$$ exits the grid on the right.
This means that if the target that it hits in on row $$$r$$$, there is no other target to its right on row $$$r$$$.
For columns with $$$a_j=2$$$, the boomerang in column $$$j$$$ has to hit second target in some column $$$k$$$ before moving downwards.
The $$$2$$$ targets that this boomerang hits must be in the same row, and since no row contains more than $$$2$$$ targets, these are the only $$$2$$$ targets in the row. Additionally, there isn't any target below the second target. This means $$$a_k=1$$$.
This tells us that columns $$$j$$$ with $$$a_j=2$$$ must be matched with columns $$$k$$$ with $$$a_k=1$$$ to its right with $$$j < k$$$. If we only had $$$a_j=1$$$ and $$$a_j=2$$$, we can simply greedily match $$$2$$$s to $$$1$$$s that are available.
$$$3$$$s initially seem difficult to handle. The key observation is that $$$3$$$s can "link" to $$$3$$$s to its right. The way to do this for the have the first target for one boomerang be the third target for another boomerang.
This allows us to "chain" the $$$3$$$s together in one long chain.
Thus, we only care about the first $$$3$$$, which has to use either a $$$2$$$ or a $$$1$$$ (if it uses a $$$1$$$, that $$$1$$$ cannot be matched with a $$$2$$$). We should always use a $$$2$$$ if possible since it will never be used by anything else, and the exact $$$1$$$ that we use also doesn't matter.
Thus the solution is as follows: Process from right to left. If the current value is a $$$1$$$, add it to a list of available ones. If the current value is a $$$2$$$, match it with an available $$$1$$$ and remove the $$$1$$$ from the list. If the current value is a $$$3$$$, match it with $$$3$$$,$$$2$$$ or $$$1$$$ in that order of preference.
Once we have found the chains and matches, we can go from left to right and give each chain / match some number of rows to use so that they do not overlap. The final time complexity is $$$O(n)$$$.
Bonus $$$1$$$: Show that the directly simulating the path of each boomerang is overall $$$O(n)$$$.
Bonus $$$2$$$ (unsolved): Solve for $$$0 \leq a_j \leq 4$$$.