Дарий Великий строит $$$n$$$ каменных колонн, каждая из которых состоит из основания и либо $$$0$$$, либо $$$1$$$, либо $$$2$$$ фрагментов надписей, расположенных сверху.
На каждом ходе Дарий может выбрать две колонны $$$u$$$ и $$$v$$$ такие, чтобы разница в количестве надписей между этими колоннами равнялась ровно $$$1$$$, и перенести одну надпись с колонны с большим количеством надписей на другую. Гарантируется, что по крайней мере одна колонна содержит ровно $$$1$$$ надпись.
Поскольку красота является главной опорой исторических зданий, Дарий хочет, чтобы колонны были расположены по возрастанию высоты. Чтобы избежать чрезмерных усилий работников, он просит вас спланировать последовательность из максимум $$$n$$$ ходов, чтобы расположить колонны в порядке неубывания высоты, исходя из количества надписей. Минимизация количества ходов не требуется.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 3000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ — количество каменных колонн ($$$1 \leq n \leq 2 \cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, где $$$a_i \in \{0,1,2\}$$$ обозначает изначальное количество надписей на $$$i$$$-й колонне. Гарантируется, что по крайней мере на одной колонне находится ровно $$$1$$$ надпись.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите целое число $$$k$$$ — количество перемещений, использованных для сортировки колонн ($$$0 \leq k \leq n$$$).
Затем выведите $$$k$$$ строк, каждая из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), представляющие индексы колонн, участвующих в $$$i$$$-м перемещении. Во время каждого хода должно выполняться $$$|a_{u_i} - a_{v_i}| = 1$$$, и одна надпись переносится с колонны с большим количеством надписей на другую.
Можно доказать, что при заданных ограничениях решение всегда существует.
340 2 0 131 2 060 1 1 2 2 2
2 2 4 2 3 2 3 1 2 3 0
Состояние колонн в первом наборе входных данных:
- Изначально: $$$0, 2, 0, 1$$$
- После первого хода: $$$0, 1, 0, 2$$$
- После второго хода: $$$0, 0, 1, 2$$$
Состояние колонн во втором наборе входных данных:
- Изначально: $$$1, 2, 0$$$
- После первого хода: $$$0, 2, 1$$$
- После второго хода: $$$0, 1, 2$$$
В третьем наборе входных данных высоты колонн уже отсортированы в порядке возрастания.
