You are given an array of integers $a_1, a_2, \ldots, a_n$ and an integer $x$.

You need to select the maximum number of elements in the array, such that for every subsegment $a_l, a_{l + 1}, \ldots, a_r$ containing strictly more than one element $(l < r)$, either:

At least one element on this subsegment is not selected, or

$a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$.


-----Input-----

The first line of input contains one integer $t$ ($1 \leq t \leq 10$): the number of test cases.

The descriptions of $t$ test cases follow, three lines per test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 50000$): the number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100000 \leq a_i \leq 100000$).

The third line contains one integer $x$ ($-100000 \leq x \leq 100000$).


-----Output-----

For each test case, print one integer: the maximum number of elements that you can select.


-----Examples-----

Input
4
5
1 2 3 4 5
2
10
2 4 2 4 2 4 2 4 2 4
3
3
-10 -5 -10
-8
3
9 9 -3
5
Output
4
8
2
2


-----Note-----

In the first example, one valid way to select the elements is $[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$. All subsegments satisfy at least one of the criteria. For example, for the subsegment $l = 1$, $r = 2$ we have that the element $2$ is not selected, satisfying the first criterion. For the subsegment $l = 3$, $r = 5$ we have $3 + 4 + 5 = 12 \ge 2 \cdot 3$, satisfying the second criterion.

We can't select all elements, because in this case for $l = 1$, $r = 2$ all elements are selected and we have $a_1 + a_2 = 3 < 2 \cdot 2$. Thus, the maximum number of selected elements is $4$.

In the second example, one valid solution is $[\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$.

In the third example, one valid solution is $[\underline{-10}, -5, \underline{-10}]$.

In the fourth example, one valid solution is $[\underline{9}, \underline{9}, -3]$.

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	a = [c - x for c in a]
	begin = True
	unchosen = 0
	sum = 0
	for i in range(n):
		if begin:
			sum = a[i]
			begin = False
		else:
			sum += a[i]
			if sum < 0:
				begin = True
				unchosen += 1
			else:
				sum = min(sum, a[i])
	print(n - unchosen)


D = input
C = int
for H in range(C(D())):
	I = C(D())
	B = list(map(C, D().split()))
	G = C(D())
	B = [A - G for A in B]
	A = 10 ** 18
	E = 0
	for F in B:
		A += F
		if A < 0:
			A = 10 ** 18
		else:
			E += 1
			A = min(A, F)
	print(E)


import sys
input = sys.stdin.readline

def ri():
	return int(input())

def rf():
	return list(map(float, input().split()))

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

def rs():
	return input().rstrip()

def out_list(x):
	return ' '.join(map(str, x))

def solve_case():
	n = ri()
	A = rl()
	x = ri()
	res = 0
	j = 0
	for i in range(n):
		ok = True
		if i - j >= 1 and A[i - 1] + A[i] < 2 * x:
			ok = False
		if i - j >= 2 and A[i - 2] + A[i - 1] + A[i] < 3 * x:
			ok = False
		if not ok:
			res += 1
			j = i + 1
	print(n - res)
T = ri()
for ti in range(1, T + 1):
	solve_case()


epsilon = 10 ** (-6)
t = int(input())
for k in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	x = int(input())
	l = [a - x for a in l]
	s = 0
	not_choose = 0
	new_subseg = False
	for i in range(n):
		if not new_subseg:
			s = l[i]
			new_subseg = True
		else:
			s += l[i]
			if s < 0:
				not_choose += 1
				new_subseg = False
			else:
				s = min(s, l[i])
	print(n - not_choose)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	ans = 0
	Sum = 2e+18
	for i in a:
		Sum += i - x
		if Sum < 0:
			Sum = 2e+18
		else:
			Sum = min(Sum, i - x)
			ans += 1
	print(ans)


def solver():
	n = int(input())
	for _ in range(n):
		len_input = int(input())
		(*array,) = map(int, input().split())
		x = int(input())
		incriminated = set()
		for i in range(1, len_input):
			if i == 1:
				if array[i - 1] + array[i] < x * 2:
					incriminated.add(i)
			elif i - 2 in incriminated:
				if i - 1 in incriminated:
					continue
				elif array[i - 1] + array[i] < 2 * x:
					incriminated.add(i)
			elif not i - 1 in incriminated:
				if array[i - 2] + array[i - 1] + array[i] < 3 * x:
					incriminated.add(i)
				if array[i - 1] + array[i] < 2 * x:
					incriminated.add(i)
		print(len_input - len(incriminated))
solver()


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
import bisect

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = int(input())
	bi = -1
	c = 0
	for i in range(n):
		if i - 1 > bi and a[i - 1] + a[i] < x * 2:
			bi = i
			c += 1
			continue
		if i - 2 > bi and sum(a[i - 2:i + 1]) < x * 3:
			bi = i
			c += 1
	print(n - c)


def Rep_Edges(n, l, x):
	i = 0
	while i < n:
		l[i] = l[i] - x
		i = i + 1
	ans = n
	j = -1
	for i in range(1, n):
		if (i - 1 > j) & (l[i] + l[i - 1] < 0):
			ans = ans - 1
			j = i
		elif (i - 2 > j) & (l[i] + l[i - 1] + l[i - 2] < 0):
			ans = ans - 1
			j = i
	return ans
t = int(input())
ls = []
ln = []
la = []
lx = []
for i in range(t):
	n = int(input())
	s = str(input())
	x = int(input())
	ln.append(n)
	ls.append(s)
	lx.append(x)
for i in range(len(ls)):
	n = ln[i]
	s = ls[i]
	x = lx[i]
	l = []
	for j in s.split(' '):
		l.append(int(j))
	ans = Rep_Edges(n, l, x)
	la.append(ans)
for a in la:
	print(a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	ans = 0
	for i in range(n):
		a[i] -= x
	sa = [a[0]]
	for i in range(1, n):
		sa.append(sa[-1] + a[i])
	i = 1
	l = a[0]
	while i < n:
		if l + a[i] < 0:
			ans += 1
			i += 1
			if i < n:
				l = a[i]
		else:
			l = min(a[i], l + a[i])
		i += 1
	print(n - ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		l[i] -= x
	l1 = [0]
	m = 0
	for i in range(n):
		m += l[i]
		l1.append(m)
	high = -1000000
	high1 = -1000000
	h1 = -1
	m = 0
	cur = 0
	for i in range(n):
		if i - 1 >= cur:
			if l[i] + l[i - 1] < 0:
				cur = i + 1
				m += 1
		if i - 2 >= cur:
			if l[i] + l[i - 1] + l[i - 2] < 0:
				cur = i + 1
				m += 1
	print(n - m)


tt = int(input())
for TC in range(tt):
	n = int(input())
	a = [int(x) for x in input().split()]
	x = int(input())
	for i in range(n):
		a[i] -= x
	v = []
	for i in range(1, n):
		if a[i] + a[i - 1] < 0:
			v.append((i, 2))
	for i in range(2, n):
		if a[i] + a[i - 1] >= 0 and a[i - 1] + a[i - 2] >= 0 and (a[i] + a[i - 1] + a[i - 2] < 0):
			v.append((i, 3))
	v.sort()
	if len(v) == 0:
		print(n)
		continue
	deleted = 0
	cnt = 1
	for i in range(1, len(v)):
		if v[i][0] - v[i][1] + 1 == v[i - 1][0]:
			cnt += 1
		else:
			deleted += (cnt + 1) // 2
			cnt = 1
	deleted += (cnt + 1) // 2
	print(n - deleted)