Дан массив \(a\) длины \(n\), элементы которого равны \(-1\) и \(1\). Назовём массив \(a\) хорошим, если одновременно выполняются следующие условия:
- \(a_1 + a_2 + \ldots + a_n \ge 0\);
- \(a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1\).
За одну операцию вы можете выбрать произвольный элемент массива \(a_i\) и изменить его значение на противоположное. Другими словами, если \(a_i = -1\), то вы можете присвоить значение \(a_i := 1\), а если \(a_i = 1\), то присвоить значение \(a_i := -1\).
Определите минимальное количество операций, которые нужно сделать, чтобы массив \(a\) стал хорошим. Можно показать, что это всегда возможно.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, которое нужно сделать, чтобы сделать массив \(a\) хорошим.
Примечание
В первом наборе входных данных мы можем присвоить значение \(a_1 := 1\). Тогда \(a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0\) и \(a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1\). Таким образом, мы сделали \(1\) операцию.
Во втором наборе входных данных мы можем присвоить \(a_1 := 1\). Тогда \(a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0\) и \(a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1\). Таким образом, мы сделали \(1\) операцию.
В третьем наборе входных данных \(a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0\) и \(a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1\). Таким образом, все условия уже выполнены и можно не делать операции.
В четвёртом наборе входных данных мы можем присвоить значения \(a_1 := 1, a_2 := 1, a_3 := 1\). Тогда \(a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0\) и \(a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1\). Таким образом, мы сделали \(3\) операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4
-1 -1 1 -1
5
-1 -1 -1 1 1
4
-1 1 -1 1
3
-1 -1 -1
5
1 1 1 1 1
1
-1
2
-1 -1
|
1
1
0
3
0
1
2
|