CF1779C.Least Prefix Sum

Baltic, a famous chess player who is also a mathematician, has an array $a_1,a_2, \ldots, a_n$, and he can perform the following operation several (possibly $0$) times:

• Choose some index $i$ ($1 \leq i \leq n$);
• multiply $a_i$ with $-1$, that is, set $a_i := -a_i$.

Baltic's favorite number is $m$, and he wants $a_1 + a_2 + \cdots + a_m$ to be the smallest of all non-empty prefix sums. More formally, for each $k = 1,2,\ldots, n$ it should hold that $$a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m.$$

Please note that multiple smallest prefix sums may exist and that it is only required that $a_1 + a_2 + \cdots + a_m$ is one of them.

Help Baltic find the minimum number of operations required to make $a_1 + a_2 + \cdots + a_m$ the least of all prefix sums. It can be shown that a valid sequence of operations always exists.

著名国际象棋选手兼数学家 Baltic 拥有一个数组 $a_1,a_2, \ldots, a_n$，他可以执行以下操作若干次（可能为 $0$ 次）：

• 选择某个下标 $i$（满足 $1 \leq i \leq n$）；
• 将 $a_i$ 乘以 $-1$，即令 $a_i := -a_i$。

Baltic 最钟爱的数字是 $m$，他希望前 $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$ 是其中之一即可。

请帮助 Baltic 找出使 $a_1 + a_2 + \cdots + a_m$ 成为所有前缀和中最小值所需的最少操作次数。可以证明，总存在满足条件的操作序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 2\cdot 10^5$) — the size of Baltic's array and his favorite number.

The second line contains $n$ integers $a_1,a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 2\cdot 10^5$）—— 分别表示 Baltic 数组的大小及其最喜爱的数字。

第二行包含 $n$ 个整数 $a_1,a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）—— 即该数组。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, print a single integer — the minimum number of required operations.

对于每个测试用例，输出一个整数——所需的最少操作次数。

In the first example, we perform the operation $a_4 := -a_4$. The array becomes $[-1,-2,-3,4]$ and the prefix sums, $[a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]$, are equal to $[-1,-3,-6,-2]$. Thus $a_1 + a_2 + a_3=-6$ is the smallest of all prefix sums.

In the second example, we perform the operation $a_3 := -a_3$. The array becomes $[1,2,-3,4]$ with prefix sums equal to $[1,3,0,4]$.

In the third and fourth examples, $a_1 + a_2 + \cdots + a_m$ is already the smallest of the prefix sums — no operation needs to be performed.

In the fifth example, a valid sequence of operations is:

• $a_3 := -a_3$,
• $a_2 := -a_2$,
• $a_5 := -a_5$.

The array becomes $[-2,-3,5,-5,20]$ and its prefix sums are $[-2,-5,0,-5,15]$. Note that $a_1+a_2=-5$ and $a_1+a_2+a_3+a_4=-5$ are both the smallest of the prefix sums (and this is a valid solution).

在第一个例子中，我们执行操作 $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$ 均为前缀和中的最小值（这是一个合法解）。