Дарий Великий строит \(n\) каменных колонн, каждая из которых состоит из основания и либо \(0\), либо \(1\), либо \(2\) фрагментов надписей, расположенных сверху.
На каждом ходе Дарий может выбрать две колонны \(u\) и \(v\) такие, чтобы разница в количестве надписей между этими колоннами равнялась ровно \(1\), и перенести одну надпись с колонны с большим количеством надписей на другую. Гарантируется, что по крайней мере одна колонна содержит ровно \(1\) надпись.
Поскольку красота является главной опорой исторических зданий, Дарий хочет, чтобы колонны были расположены по возрастанию высоты. Чтобы избежать чрезмерных усилий работников, он просит вас спланировать последовательность из максимум \(n\) ходов, чтобы расположить колонны в порядке неубывания высоты, исходя из количества надписей. Минимизация количества ходов не требуется.
Выходные данные
Для каждого набора входных данных выведите целое число \(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\), и одна надпись переносится с колонны с большим количеством надписей на другую.
Можно доказать, что при заданных ограничениях решение всегда существует.
Примечание
Состояние колонн в первом наборе входных данных:
- Изначально: \(0, 2, 0, 1\)
- После первого хода: \(0, 1, 0, 2\)
- После второго хода: \(0, 0, 1, 2\)
Состояние колонн во втором наборе входных данных:
- Изначально: \(1, 2, 0\)
- После первого хода: \(0, 2, 1\)
- После второго хода: \(0, 1, 2\)
В третьем наборе входных данных высоты колонн уже отсортированы в порядке возрастания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
0 2 0 1
3
1 2 0
6
0 1 1 2 2 2
|
2
2 4
2 3
2
3 1
2 3
0
|