Вам дан массив целых чисел \(a_1, a_2, \dots, a_n\). Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- Выбрать любой элемент \(a_i\) из массива и заменить его значение на любое целое число от \(0\) до \(a_i\) (включительно). Более формально, если \(a_i < 0\), заменить \(a_i\) на любое целое число из \([a_i, 0]\), иначе заменить \(a_i\) на любое целое число из \([0, a_i]\).
Пусть \(r\) — минимально возможное произведение всех \(a_i\) после выполнения операции любое число раз.
Найдите минимальное количество операций, необходимое для того, чтобы произведение стало равно \(r\). Также выведите одну такую кратчайшую последовательность операций. Если существует несколько ответов, можете вывести любой из них.
Выходные данные
Для каждого набора входных данных:
- Первая строка должна содержать минимальное количество операций \(k\) (\(0 \leq k \leq n\)).
- \(j\)-я из следующих \(k\) строк должна содержать два целых числа \(i\) и \(x\), которые описывают \(j\)-ю операцию. Эта операция заключается в замене \(a_i\) на \(x\).
Примечание
В первом примере мы можем заменить значение первого элемента на \(0\), и произведение станет \(0\), что является минимально возможным произведением.
Во втором примере изначально произведение целых чисел равно \(2 \cdot 8 \cdot (-1) \cdot 3 = -48\), что является минимально возможным произведением, поэтому в этом случае ничего делать не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30
|
1
1 0
0
0
1
3 0
|