Baltic是一位著名的国际象棋棋手,同时也是一位数学家,他有一个数组$$$a_1,a_2, \ldots, a_n$$$,他可以执行以下操作多次(可能是$$$0$$$):
- 选择一些索引 $$$i$$$ ($$$1 \leq i \leq n$$$);
- 将 $$$a_i$$$ 与 $$$-1$$$ 相乘,即设置 $$$a_i := -a_i$$$。
Baltic 最喜欢的数字是 $$$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$$$ 成为所有前缀和最少所需的最少操作数。可以证明,有效的操作序列始终存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 所需操作的最少数量。
示例
输入 #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 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$$$ 都是最小的前缀和(这是一个有效的解决方案)。