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.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10000$). 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$.


-----Output-----

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


-----Examples-----

Input
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
Output
1
1
0
0
3
4


-----Note-----

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).

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms


Solutions:
import sys, heapq
input = lambda : sys.stdin.readline().rstrip()

def calc(A):
	(q, s, ans) = ([], 0, 0)
	for i in A:
		s += i
		heapq.heappush(q, i)
		while s < 0:
			s -= 2 * heapq.heappop(q)
			ans += 1
	return ans

def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	return calc(list(map(lambda a: -a, A[m - 1:0:-1]))) + calc(A[m:])
T = int(input())
for i in range(T):
	print(solve())


import sys
import heapq

def solve():
	inp = sys.stdin.readline
	push = heapq.heappush
	pop = heapq.heappop
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	res = 0
	if m != 1 and a[m - 1] > 0:
		res += 1
		a[m - 1] = -a[m - 1]
	if m != 1:
		cur = 0
		can = []
		for i in range(m - 1, 0, -1):
			v = a[i]
			cur -= v
			if v > 0:
				push(can, -v)
			while cur < 0:
				mm = -can[0]
				pop(can)
				cur += 2 * mm
				res += 1
	can = []
	cur = 0
	for i in range(m, n):
		v = a[i]
		cur += v
		if v < 0:
			push(can, v)
		while cur < 0:
			mm = can[0]
			pop(can)
			cur -= 2 * mm
			res += 1
	print(res)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
import heapq
input = sys.stdin.readline

def findminlen(a):
	s = 0
	h = []
	ans = 0
	for i in range(len(a) - 1, -1, -1):
		s += a[i]
		if a[i] > 0:
			heapq.heappush(h, -1 * a[i])
		while s > 0:
			if len(h) == 0:
				break
			g = heapq.heappop(h)
			s += 2 * g
			ans += 1
	return ans

def findmnlen(a):
	s = 0
	h = []
	ans = 0
	for i in range(len(a)):
		s += a[i]
		if a[i] < 0:
			heapq.heappush(h, a[i])
		while s < 0:
			if len(h) == 0:
				break
			g = heapq.heappop(h)
			s += -2 * g
			ans += 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	ans += findminlen(a[1:m])
	ans += findmnlen(a[m:])
	print(ans)


import sys
from heapq import *
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		cnt = 0
		i = m
		sum = 0
		H = []
		while i < n:
			sum += A[i]
			heappush(H, A[i])
			while sum < 0:
				cnt += 1
				sum += -2 * heappop(H)
			i += 1
		i = m - 1
		sum = 0
		H = []
		while i >= 1:
			sum += A[i]
			heappush(H, -A[i])
			while sum > 0:
				cnt += 1
				sum += 2 * heappop(H)
			i -= 1
		print(cnt)


import heapq

def fun(n, m, l):
	if n == 1:
		print(0)
		return
	hp = []
	heapq.heapify(hp)
	cnt = 0
	sum = 0
	for i in range(m, n):
		sum = sum + l[i]
		heapq.heappush(hp, l[i])
		while sum < 0:
			sum = sum - 2 * hp[0]
			cnt = cnt + 1
			d = hp[0]
			heapq.heappop(hp)
	hp = []
	heapq.heapify(hp)
	sum = 0
	for i in range(m - 1):
		sum = sum + l[m - 1 - i]
		heapq.heappush(hp, -l[m - 1 - i])
		while sum > 0:
			sum = sum + 2 * hp[0]
			cnt = cnt + 1
			d = hp[0]
			heapq.heappop(hp)
	print(cnt)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	fun(n, m, l)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n, m):
	if n == 1:
		return 0
	ans = 0
	if m > 1 and a[m - 1] > 0:
		ans += 1
		a[m - 1] *= -1
	sm = sum(a[:m])
	si = sm
	q = []
	for i in range(m - 1, 0, -1):
		si -= a[i]
		if a[i] > 0:
			heapq.heappush(q, -a[i])
		while si < sm:
			ans += 1
			sm += 2 * heapq.heappop(q)
	q = []
	(si, sm) = (0, 0)
	for i in range(m + 1, n + 1):
		si += a[i - 1]
		if a[i - 1] < 0:
			heapq.heappush(q, a[i - 1])
		while si < sm:
			ans += 1
			si -= 2 * heapq.heappop(q)
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, n, m))


import heapq
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	xs = list(map(int, input().split()))
	ans = 0
	post = []
	s = 0
	for x in xs[m:]:
		heapq.heappush(post, x)
		s += x
		while s < 0:
			ans += 1
			t = heapq.heappop(post)
			s += -2 * t
			heapq.heappush(post, -t)
	pred = []
	s = 0
	for x in xs[1:m][::-1]:
		heapq.heappush(pred, -x)
		s += -x
		while s < 0:
			ans += 1
			t = heapq.heappop(pred)
			s += -2 * t
			heapq.heappush(pred, -t)
	print(ans)


from heapq import heapify, heappop, heappush
for tcase in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	(s, pq) = (0, [])
	for i in range(m, n):
		s += a[i]
		heappush(pq, a[i])
		while s < 0:
			s -= 2 * heappop(pq)
			ans += 1
	(s, pq) = (0, [])
	for i in reversed(range(1, m)):
		s += a[i]
		heappush(pq, -a[i])
		while s > 0:
			s += 2 * heappop(pq)
			ans += 1
	print(ans)


import heapq

def count1(a):
	heap = []
	heapq.heapify(heap)
	cur_sum = 0
	count = 0
	for i in range(len(a)):
		cur_sum += a[i]
		heapq.heappush(heap, -a[i])
		while cur_sum > 0:
			tmp = -heapq.heappop(heap)
			cur_sum -= 2 * tmp
			heapq.heappush(heap, tmp)
			count += 1
	return count

def count2(a):
	heap = []
	heapq.heapify(heap)
	cur_sum = 0
	count = 0
	for i in range(len(a)):
		cur_sum += a[i]
		heapq.heappush(heap, a[i])
		while cur_sum < 0:
			tmp = heapq.heappop(heap)
			cur_sum -= 2 * tmp
			heapq.heappush(heap, -tmp)
			count += 1
	return count

def solve(a, m):
	ans = count1(a[1:m][::-1]) + count2(a[m:])
	print(ans)
	return
t = int(input())
for i in range(t):
	s = input()
	(n, m) = (int(s.split()[0]), int(s.split()[1]))
	a = [int(si) for si in input().split()]
	solve(a, m)


import heapq

def main():
	res = 0
	pre = 0
	q = []
	for i in range(m + 1, n):
		pre += a[i]
		if a[i] < 0:
			heapq.heappush(q, a[i])
		while pre < 0:
			res += 1
			pre -= 2 * heapq.heappop(q)
	pre = 0
	q = []
	for i in range(m, 0, -1):
		pre += a[i]
		if a[i] > 0:
			heapq.heappush(q, -a[i])
		while pre > 0:
			res += 1
			pre += 2 * heapq.heappop(q)
	return res
t = int(input())
for case in range(t):
	(n, m) = map(int, input().split())
	m -= 1
	a = list(map(int, input().split()))
	print(main())


import heapq

def LPS(n, m, strs):
	if n == 1:
		return 0
	h = []
	heapq.heapify(h)
	(cnt, pm) = (0, 0)
	cur_m = m
	while cur_m < n - 1:
		pm = pm + strs[cur_m + 1]
		heapq.heappush(h, strs[cur_m + 1])
		if pm < 0:
			x = heapq.heappop(h)
			pm = pm - 2 * x
			cnt = cnt + 1
		cur_m = cur_m + 1
	h = []
	heapq.heapify(h)
	pm = 0
	A = strs[:m + 1]
	A.reverse()
	for i in range(m):
		pm = pm + A[i]
		heapq.heappush(h, -A[i])
		if pm > 0:
			x = heapq.heappop(h)
			pm = pm + 2 * x
			cnt = cnt + 1
	new_pm = pm + A[m]
	if new_pm > 0:
		if new_pm > A[m]:
			cnt = cnt + 1
	return cnt
x = int(input())
for i in range(x):
	nm = list(map(int, input().split()))
	(n, m) = (nm[0], nm[1] - 1)
	s = list(map(int, input().split()))
	print(LPS(n, m, s))


import heapq
for _ in range(int(input())):
	[n, m] = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	ans = 0
	s = 0
	h = []
	for i in range(m, n):
		if arr[i] < 0:
			heapq.heappush(h, arr[i])
		s += arr[i]
		if s < 0:
			s -= 2 * heapq.heappop(h)
			ans += 1
	h = []
	s = 0
	for i in range(m - 1, 0, -1):
		if arr[i] > 0:
			heapq.heappush(h, -1 * arr[i])
		s += arr[i]
		if s > 0:
			s -= -2 * heapq.heappop(h)
			ans += 1
	print(ans)


import heapq

def least_prefix_sum(n, m, nums):
	index: int = m - 1
	operation_count: int = 0
	cur_sum = 0
	heap = []
	while index >= 1:
		if nums[index] > 0:
			heapq.heappush(heap, -1 * nums[index])
		if cur_sum + nums[index] > 0:
			cur_sum += 2 * heap[0]
			heapq.heappop(heap)
			operation_count += 1
		cur_sum += nums[index]
		index -= 1
	cur_sum = 0
	heap = []
	index = m
	while index < len(nums):
		if nums[index] < 0:
			heapq.heappush(heap, nums[index])
		if cur_sum + nums[index] < 0:
			cur_sum -= 2 * heap[0]
			heapq.heappop(heap)
			operation_count += 1
		cur_sum += nums[index]
		index += 1
	return operation_count
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	nums = input().split(' ')
	nums = [int(x) for x in nums]
	print(least_prefix_sum(n, m, nums))


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
import heapq

def min_heap_compare(element1, element2):
	if element1 > element2:
		return True
	return False

def max_heap_compare(element1, element2):
	if element1 < element2:
		return True
	return False
tests = inp()
for i in range(tests):
	(n, m) = invr()
	arr = inlt()
	ans = 0
	max_heap = []
	prefix_sum = 0
	for j in range(m - 1, 0, -1):
		prefix_sum += arr[j]
		heapq.heappush(max_heap, -arr[j])
		if prefix_sum > 0:
			val = heapq.heappop(max_heap)
			prefix_sum += 2 * val
			ans += 1
	min_heap = []
	prefix_sum = 0
	for j in range(m, n):
		prefix_sum += arr[j]
		heapq.heappush(min_heap, arr[j])
		if prefix_sum < 0:
			val = heapq.heappop(min_heap)
			prefix_sum += -2 * val
			ans += 1
	print(ans)


import heapq
T = int(input())
while T > 0:
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	val = 0
	heap = []
	ret = 0
	for i in range(m - 1, 0, -1):
		val += A[i]
		if A[i] > 0:
			heapq.heappush(heap, -A[i])
			while val > 0:
				t = heapq.heappop(heap)
				val += 2 * t
				ret += 1
	heap = []
	val = 0
	for i in range(m, n):
		val += A[i]
		if A[i] < 0:
			heapq.heappush(heap, A[i])
			while val < 0:
				t = heapq.heappop(heap)
				val -= 2 * t
				ret += 1
	print(ret)
	T -= 1


from heapq import heappop, heappush
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	hp = []
	run = 0
	final = 0
	for i in range(m, n):
		run += arr[i]
		if arr[i] < 0:
			heappush(hp, arr[i])
		if run < 0:
			final += 1
			run -= 2 * heappop(hp)
	hp = []
	run = 0
	for i in reversed(range(1, m)):
		arr[i] = -arr[i]
		run += arr[i]
		if arr[i] < 0:
			heappush(hp, arr[i])
		if run < 0:
			final += 1
			run -= 2 * heappop(hp)
	print(final)


import heapq
from itertools import accumulate

def first_func(arr: list, pre: list, m: int) -> int:
	hp = list()
	ths = pre[m + 1]
	cnt = 0
	for i in range(m + 1, 0, -1):
		while pre[i] < ths:
			tmp = heapq.heappop(hp)
			ths += 2 * tmp
			cnt += 1
		heapq.heappush(hp, -1 * arr[i - 1])
	return cnt

def second_func(arr: list, pre: list, n: int, m: int) -> int:
	hp = list()
	ths = pre[m + 1]
	cnt = 0
	for i in range(m + 2, n + 1):
		heapq.heappush(hp, arr[i - 1])
		while pre[i] < ths:
			tmp = heapq.heappop(hp)
			ths += 2 * tmp
			cnt += 1
	return cnt
n = int(input())
while n > 0:
	n -= 1
	(k, m) = list(map(int, input().split()))
	m -= 1
	arr = list(map(int, input().split()))
	pre = [0] + list(accumulate(arr))
	print(first_func(arr, pre, m) + second_func(arr, pre, k, m))


import heapq

def solve(N, m, nums):
	ans = 0
	(arr, ps) = ([], 0)
	for i in range(m, 0, -1):
		ps += nums[i]
		heapq.heappush(arr, -nums[i])
		while ps > 0:
			a = -heapq.heappop(arr)
			ps -= a + a
			ans += 1
	(arr, ps) = ([], 0)
	for i in range(m + 1, N):
		ps += nums[i]
		heapq.heappush(arr, nums[i])
		while ps < 0:
			a = heapq.heappop(arr)
			ps -= a + a
			ans += 1
	return ans
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	print(solve(N, M - 1, nums))


import heapq
from itertools import accumulate
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	m -= 1
	arr = list(map(int, input().split(' ')))
	pref = list(accumulate(arr))
	cur = pref[m]
	heap = []
	op = 0
	for i in range(m, -1, -1):
		if pref[i] < cur and heap:
			cur += 2 * heapq.heappop(heap)
			op += 1
		heapq.heappush(heap, -arr[i])
	heap = []
	cur = pref[m]
	for i in range(m + 1, n):
		heapq.heappush(heap, arr[i])
		if pref[i] < cur and heap:
			cur += 2 * heapq.heappop(heap)
			op += 1
	print(op)


import heapq
iter = int(input())
for _ in range(iter):
	(n, m) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	op = 0
	heap = []
	addheap = []
	if a[m - 1] > 0 and m != 1:
		a[m - 1] = -a[m - 1]
		op += 1
	pre = sum(a[:m + 1])
	s = pre
	heapq.heapify(heap)
	heapq.heapify(addheap)
	for i in range(m - 2, -1, -1):
		s -= a[i + 1]
		if s < pre:
			while s < pre:
				pre += heapq.heappop(heap)
				op += 1
		if a[i] > 0:
			heapq.heappush(heap, -2 * a[i])
	s = pre
	for i in range(m, n):
		s += a[i]
		if a[i] < 0:
			heapq.heappush(addheap, a[i])
		if s < pre:
			while s < pre:
				s -= 2 * heapq.heappop(addheap)
				op += 1
	print(op)


t = int(input())
import heapq
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	sums = sum(a[:m])
	lin = sums
	res = 0
	ans = []
	for i in range(m - 1, 0, -1):
		lin -= a[i]
		if a[i] > 0:
			heapq.heappush(ans, -a[i])
		if lin < sums:
			sums += 2 * heapq.heappop(ans)
			res += 1
	lin = 0
	ans = []
	for i in range(m, n):
		lin += a[i]
		if a[i] < 0:
			heapq.heappush(ans, a[i])
		if lin < 0:
			lin -= 2 * heapq.heappop(ans)
			res += 1
	print(res)


import heapq

def first_func(arr: list, pre: list, m: int) -> int:
	hp = list()
	ths = pre[m + 1]
	cnt = 0
	for i in range(m + 1, 0, -1):
		while pre[i] < ths:
			tmp = heapq.heappop(hp)
			assert tmp <= 0
			ths += 2 * tmp
			cnt += 1
		heapq.heappush(hp, -1 * arr[i - 1])
	return cnt

def second_func(arr: list, pre: list, n: int, m: int) -> int:
	hp = list()
	ths = pre[m + 1]
	cnt = 0
	for i in range(m + 2, n + 1):
		heapq.heappush(hp, arr[i - 1])
		while pre[i] < ths:
			tmp = heapq.heappop(hp)
			assert tmp <= 0
			ths += 2 * tmp
			cnt += 1
	return cnt
n = int(input())
while n > 0:
	n -= 1
	(k, m) = list(map(int, input().split()))
	m -= 1
	arr = list(map(int, input().split()))
	pre = list()
	pre.append(0)
	for i in range(0, arr.__len__()):
		pre.append(arr[i] + pre[i])
	print(first_func(arr, pre, m) + second_func(arr, pre, k, m))


import heapq

def heappush(heap, item):
	return heapq.heappush(heap, -item)

def heappop(heap):
	return -heapq.heappop(heap)
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if n == 1:
		print('0')
		continue
	(opr, summ) = (0, 0)
	hea1 = []
	heapq.heapify(hea1)
	for i in range(m, n):
		if arr[i] < 0:
			heappush(hea1, -arr[i])
		summ += arr[i]
		while summ < 0:
			temp = -heappop(hea1)
			temp = -temp
			summ += temp * 2
			opr += 1
	if arr[m - 1] <= 0:
		summ = arr[m - 1]
	elif m != 1:
		summ = -arr[m - 1]
		opr += 1
	temp = 0
	hea2 = []
	heapq.heapify(hea2)
	for i in range(m - 2, 0, -1):
		if arr[i] > 0:
			heappush(hea2, arr[i])
		summ += arr[i]
		while summ > 0:
			temp = heappop(hea2)
			temp = -temp
			summ += temp * 2
			opr += 1
	print(opr)


import heapq
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	m_sum = 0
	lst = []
	temp = []
	temp.append(arr[0])
	for i in range(1, n):
		temp.append(temp[i - 1] + arr[i])
	temp_sum = temp[m - 1]
	count = 0
	heapq.heapify(lst)
	for i in range(m - 1, -1, -1):
		while temp[i] < temp_sum:
			tp = -1 * heapq.heappop(lst)
			temp_sum = temp_sum - 2 * tp
			count = count + 1
		heapq.heappush(lst, -1 * arr[i])
	li = []
	temp_sum = temp[m - 1]
	heapq.heapify(li)
	for i in range(m, n):
		heapq.heappush(li, arr[i])
		while temp[i] < temp_sum:
			item = heapq.heappop(li)
			temp_sum = temp_sum + 2 * item
			count = count + 1
	print(count)
	t = t - 1


import heapq
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	a = [int(i) for i in input().strip().split()]
	op = 0
	curr_sum = 0
	if a[m - 1] <= 0:
		curr_sum = a[m - 1]
	elif m != 1:
		curr_sum = -1 * a[m - 1]
		a[m - 1] = -1 * a[m - 1]
		op += 1
	pos = []
	temp = 0
	for i in range(m - 2, 0, -1):
		if a[i] > 0:
			heapq.heappush(pos, (-a[i], i))
		curr_sum += a[i]
		while curr_sum > 0:
			(ele, ind) = heapq.heappop(pos)
			curr_sum += 2 * ele
			a[ind] = ele
			op += 1
	val = curr_sum
	pos = []
	for i in range(m, n):
		if a[i] < 0:
			heapq.heappush(pos, (a[i], i))
		curr_sum += a[i]
		while curr_sum < val:
			(ele, ind) = heapq.heappop(pos)
			curr_sum -= 2 * ele
			a[ind] = -ele
			op += 1
	print(op)


import heapq
import math
eps = 10 ** (-9)

def solve():
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	a = input().split(' ')
	a = [int(x) for x in a]
	p = [0]
	ans = 0
	mini = float('inf')
	for i in range(len(a)):
		p.append(a[i] + p[i])
		mini = min(mini, p[i + 1])
	if p[m] == mini:
		print(ans)
		return
	z = []
	accum = 0
	for i in range(m + 1, len(p)):
		if a[i - 1] < 0:
			a[i - 1] = -a[i - 1]
			heapq.heappush(z, -a[i - 1])
		p[i] += accum
		x = p[i]
		while x < p[m]:
			y = -heapq.heappop(z)
			x += 2 * y
			ans += 1
			accum += 2 * y
		p[i] = x
	if p[m] == min(p):
		print(ans)
		return
	z = []
	for i in range(m - 1, 0, -1):
		if a[i] > 0:
			a[i] = -a[i]
			heapq.heappush(z, a[i])
		while p[i] < p[m]:
			y = heapq.heappop(z)
			p[m] += 2 * y
			ans += 1
	print(ans)
	return
t = int(input())
for _ in range(t):
	solve()


from queue import PriorityQueue as pq

def intl(l):
	return list(map(int, l))

def solve():
	(n, m) = map(int, input().split())
	m -= 1
	a = intl(input().split())
	psum = [a[0]]
	for i in range(1, n):
		psum.append(a[i] + psum[-1])
	op = 0
	ch = 0
	post = pq()
	for i in range(m + 1, n):
		if a[i] < 0:
			post.put(a[i])
		while psum[i] + ch < psum[m]:
			x = post.get()
			ch -= 2 * x
			op += 1
	ch = 0
	pre = pq()
	for i in range(m, -1, -1):
		while psum[i] < psum[m] + ch:
			x = pre.get()
			ch += 2 * x
			op += 1
		if a[i] > 0:
			pre.put(-a[i])
	return op
t = int(input())
for _ in range(t):
	print(solve())


import itertools
from queue import PriorityQueue

def solve_left(arr):
	curr_sum = 0
	changes_nr = 0
	positives_pq = PriorityQueue()
	for elem in arr:
		curr_sum += elem
		if elem > 0:
			positives_pq.put(-elem)
		while curr_sum > 0 and (not positives_pq.empty()):
			to_modify = -positives_pq.get()
			curr_sum -= 2 * to_modify
			changes_nr += 1
	return changes_nr

def solve_right(arr):
	curr_sum = 0
	changes_nr = 0
	negatives_pq = PriorityQueue()
	for elem in arr:
		curr_sum += elem
		if elem < 0:
			negatives_pq.put(elem)
		while curr_sum < 0 and (not negatives_pq.empty()):
			to_modify = negatives_pq.get()
			curr_sum -= 2 * to_modify
			changes_nr += 1
	return changes_nr

def run():
	(n, m) = (int(x) for x in input().split())
	m -= 1
	arr = [int(x) for x in input().split()]
	if n == 1:
		print(0)
		return
	ans = solve_left(arr[1:m + 1][::-1]) + solve_right(arr[m + 1:])
	print(ans)
tests_nr = int(input())
for _ in range(tests_nr):
	run()


from queue import PriorityQueue
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	m -= 1
	count = 0
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i] + a[i]
	t = 0
	pq = PriorityQueue()
	pq.put(-a[m])
	for i in range(m - 1, -1, -1):
		while pre[i + 1] < pre[m + 1] + 2 * t:
			t += pq.get()
			count += 1
		pq.put(-a[i])
	t = 0
	q = PriorityQueue()
	for i in range(m + 1, n):
		q.put(a[i])
		while pre[i + 1] + 2 * t < pre[m + 1]:
			t -= q.get()
			count += 1
	print(count)