Задан массив \(a\), состоящий из \(n\) целых чисел. Вы можете выполнять следующие операции любое количество раз (возможно, нулевое):
- Выбрать пару индексов \((i, j)\) таких, что \(|i-j|=1\) (индексы \(i\) и \(j\) являются соседними) и присвоить \(a_i := a_i + |a_i - a_j|\);
- Выбрать пару индексов \((i, j)\) таких, что \(|i-j|=1\) (индексы \(i\) и \(j\) являются соседними) и присвоить \(a_i := a_i - |a_i - a_j|\).
Значение \(|x|\) означает абсолютную величину \(x\). Например, \(|4| = 4\), \(|-3| = 3\).
Ваша задача — найти минимальное количество операций, необходимых для того, чтобы получить массив, состоящий из одинаковых чисел и вывести порядок операций, чтобы это сделать.
Гарантируется, что вы всегда сможете получить массив, состоящий из одинаковых чисел, при помощи таких операций.
Заметьте, что после каждой операции каждый элемент текущего массива не должен превосходить \(10^{18}\) по абсолютной величине.
Выходные данные
В первой строке выведите одно целое число \(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}\) по абсолютной величине.
Если существует несколько возможных ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 4 6 6 6
|
2
1 2 3
1 1 2
|
|
2
|
3
2 8 10
|
2
2 2 1
2 3 2
|
|
3
|
4
1 1 1 1
|
0
|