Codeforces Round 550 (Div. 3) |
---|
Закончено |
Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вы можете выполнять следующие операции любое количество раз (возможно, нулевое):
Значение $$$|x|$$$ означает абсолютную величину $$$x$$$. Например, $$$|4| = 4$$$, $$$|-3| = 3$$$.
Ваша задача — найти минимальное количество операций, необходимых для того, чтобы получить массив, состоящий из одинаковых чисел и вывести порядок операций, чтобы это сделать.
Гарантируется, что вы всегда сможете получить массив, состоящий из одинаковых чисел, при помощи таких операций.
Заметьте, что после каждой операции каждый элемент текущего массива не должен превосходить $$$10^{18}$$$ по абсолютной величине.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в $$$a$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ — $$$i$$$-й элемент $$$a$$$.
В первой строке выведите одно целое число $$$k$$$ — минимальное количество операций, необходимое для того, чтобы получить массив, состоящий из одинаковых чисел.
В следующих $$$k$$$ строках выведите сами операции. $$$p$$$-я операция должна быть выведена в виде тройки целых чисел $$$(t_p, i_p, j_p)$$$, где $$$t_p$$$ равно либо $$$1$$$, либо $$$2$$$ ($$$1$$$ означает, что Вы выполняете операцию первого типа, а $$$2$$$ означает, что Вы выполняете операцию второго типа), а $$$i_p$$$ и $$$j_p$$$ — индексы соседних элементов массива такие, что $$$1 \le i_p, j_p \le n$$$, $$$|i_p - j_p| = 1$$$. Смотрите в примеры для лучшего понимания.
Заметьте, что после каждой операции каждый элемент текущего массива не должен превосходить $$$10^{18}$$$ по абсолютной величине.
Если существует несколько возможных ответов, выведите любой.
5 2 4 6 6 6
2 1 2 3 1 1 2
3 2 8 10
2 2 2 1 2 3 2
4 1 1 1 1
0
Название |
---|