C. Наименьшая префиксная сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Балтика, известного шахматиста, а также математика, есть массив $$$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$$$ стала наименьшей префиксной суммой. Можно показать, что необходимая последовательность операций всегда существует.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 2\cdot 10^5$$$) — размер массива и его любимое число.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — сам массив.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимально необходимое число операций.

Пример
Входные данные
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
Примечание

В первом примере можно выполнить операцию $$$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$$$ — минимальные префиксные суммы (и это корректное решение).