У Балтика, известного шахматиста, а также математика, есть массив \(a_1,a_2, \ldots, a_n\), и он хочет выполнить следующую операцию несколько (возможно, \(0\)) раз:
- Выбрать индекс \(i\) (\(1 \leq i \leq n\));
- умножить \(a_i\) на \(-1\), то есть присвоить \(a_i := -a_i\).
Любимое число Балтика равно \(m\), поэтому он хочет, чтобы значение \(a_1 + a_2 + \cdots + a_m\) было наименьшим среди всех непустых префиксных сумм. Формально, для всех \(k = 1,2,\ldots, n\) должно выполняться \(\)a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m.\(\)
Обратите внимание, что может существовать несколько наименьших префиксных сумм, и необходимо только, чтобы \(a_1 + a_2 + \cdots + a_m\) была одной из них.
Помогите Балтику найти минимальное количество операций, необходимое, чтобы сумма \(a_1 + a_2 + \cdots + a_m\) стала наименьшей префиксной суммой. Можно показать, что необходимая последовательность операций всегда существует.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально необходимое число операций.
Примечание
В первом примере можно выполнить операцию \(a_4 := -a_4\). Массив становится равным \([-1,-2,-3,4]\), а префиксные суммы \([a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]\) становятся равными \([-1,-3,-6,-2]\). Поэтому \(a_1 + a_2 + a_3=-6\) является наименьшей из всех префиксных сумм.
Во втором примере можно выполнить операцию \(a_3 := -a_3\). Массив становится равным \([1,2,-3,4]\), префиксные суммы равны \([1,3,0,4]\).
В третьем и четвертом примерах \(a_1 + a_2 + \cdots + a_m\) уже является наименьшей префиксной суммой, нет необходимости выполнять операции.
В пятом примере одна из подходящих последовательностей операций следующая:
- \(a_3 := -a_3\),
- \(a_2 := -a_2\),
- \(a_5 := -a_5\).
Массив становится равным \([-2,-3,5,-5,20]\), его префиксные суммы равны \([-2,-5,0,-5,15]\). Обратите внимание, что и \(a_1+a_2=-5\), и \(a_1+a_2+a_3+a_4=-5\) — минимальные префиксные суммы (и это корректное решение).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
|
1
1
0
0
3
4
|