Вам дан массив \(a\) из \(n\) элементов.
Вы можете выполнить следующую операцию не более \(n\) раз: выбрать три индекса \(x,y,z\) \((1 \leq x < y < z \leq n)\) и заменить \(a_x\) на \(a_y - a_z\). После операции \(|a_x|\) должно быть меньше \(10^{18}\).
Ваша цель сделать полученный массив неубывающим. Если решений несколько, можно вывести любое. Если это невозможно, вы должны сообщить об этом.
Выходные данные
Для каждого теста выведите \(-1\), если решения нет. В противном случае в первой строке выведите единственное целое число \(m\) \((0 \leq m \leq n)\) — количество выполненных вами операций.
Тогда \(i\)-я из следующих \(m\) строк должна содержать три целых числа \(x,y,z\) \((1 \leq x < y < z \leq n)\)— описание \(i\)-й операции.
Если решений несколько, можно вывести любое. Обратите внимание, что вам не нужно минимизировать количество операций в этой задаче.
Примечание
В первом примере массив становится
\([-6,-4,2,-1,2]\) после первой операции,
\([-6,-4,-3,-1,2]\) после второй операции.
Во втором примере невозможно сделать массив отсортированным ни после какой последовательности операций.
В третьем примере массив уже отсортирован, поэтому никаких операций выполнять не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
|
2
1 2 3
3 4 5
-1
0
|