This is the easy version of the problem. The only difference is that in this version $n \leq 2000$. You can make hacks only if both versions of the problem are solved.

There are $n$ potions in a line, with potion $1$ on the far left and potion $n$ on the far right. Each potion will increase your health by $a_i$ when drunk. $a_i$ can be negative, meaning that potion will decrease will health.

You start with $0$ health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 2000$) — the number of potions.

The next line contains $n$ integers $a_1$, $a_2$, ... ,$a_n$ ($-10^9 \leq a_i \leq 10^9$) which represent the change in health after drinking that potion.


-----Output-----

Output a single integer, the maximum number of potions you can drink without your health becoming negative.


-----Examples-----

Input
6
4 -4 1 -3 1 -3
Output
5


-----Note-----

For the sample, you can drink $5$ potions by taking potions $1$, $3$, $4$, $5$ and $6$. It is not possible to drink all $6$ potions because your health will go negative at some point

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Complete search

Greedy algorithms
Skill types: Dynamic programming

Data structures

Complete search

Greedy algorithms

Starter code:

Solutions:
def func():
	n = int(input())
	l = list(map(int, input().split()))
	pois = 0
	health = 0
	neg_pos = []
	for potion in l:
		if potion >= 0:
			pois += 1
			health += potion
		elif potion + health >= 0:
			pois += 1
			health += potion
			neg_pos.append(potion)
		elif neg_pos:
			mn = min(neg_pos)
			if potion > mn:
				health = health - mn + potion
				neg_pos.remove(mn)
				neg_pos.append(potion)
	return pois
t = 1
for i in range(t):
	print(func())


from heapq import heappush, heappushpop
n = int(input())
(*arr,) = map(int, input().split())
(H, sm) = ([], 0)
for x in arr:
	sm += x
	sm -= (heappushpop(H, x) if sm < 0 else heappush(H, x)) or 0
print(len(H))


n = int(input())
l1 = [int(a) for a in input().split()]
negs = []
(ctr, sm) = (0, 0)
for i in range(n):
	sm += l1[i]
	ctr += 1
	if l1[i] < 0:
		negs.append(l1[i])
		negs.sort(reverse=True)
	while sm < 0:
		sm -= negs[-1]
		negs.pop()
		ctr -= 1
print(ctr)


import heapq
n = int(input())
potions = list(map(int, input().split()))
hp = result = 0
poisons = []
for potion in potions:
	if potion >= 0:
		hp += potion
		result += 1
	elif hp + potion >= 0:
		hp += potion
		result += 1
		heapq.heappush(poisons, potion)
	else:
		if not poisons:
			continue
		if potion > poisons[0]:
			hp += potion - heapq.heappushpop(poisons, potion)
print(result)


from heapq import heapify, heappush, heappop

def T():
	return int(input())

def S():
	return str(input())

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

def M():
	return map(int, input().split(' '))
n = T()
heap = []
heapify(heap)
arr = A()
total = 0
count = 0
for i in arr:
	total += i
	heappush(heap, i)
	while total < 0:
		total -= heappop(heap)
print(len(heap))


import heapq
n = int(input())
arr = list(map(int, input().split()))
temp = []
total = 0
potions = 0
for i in arr:
	if i < 0:
		heapq.heappush(temp, i)
	total += i
	potions += 1
	while total < 0:
		total -= heapq.heappop(temp)
		potions -= 1
print(potions)


import heapq
n = int(input())
potions = list(map(int, input().split()))
minH = []
health = 0
res = 0
for p in potions:
	health += p
	if health >= 0:
		res += 1
	if p >= 0:
		continue
	heapq.heappush(minH, p)
	if health < 0:
		min_val = heapq.heappop(minH)
		health -= min_val
print(res)


import math
import bisect
n = input()
l = list(map(int, input().split()))
pot = []
curr = 0
cnt = 0
for i in l:
	if pot == []:
		if curr + i > -1:
			curr = curr + i
			pot.append(i)
			cnt += 1
	elif curr + i > -1:
		curr = curr + i
		if i < 0:
			pot.append(i)
		cnt += 1
	else:
		minn = min(pot)
		if minn < i:
			pot.remove(minn)
			if i < 0:
				pot.append(i)
			curr = curr + i - minn
print(cnt)


from heapq import heappush, heappushpop
n = int(input())
a = list(map(int, input().split()))
cnt = 0
x = 0
h = []
for d in a:
	if d >= 0:
		x += d
		cnt += 1
		continue
	if x + d >= 0:
		x += d
		cnt += 1
		heappush(h, d)
	elif h:
		y = heappushpop(h, d)
		x += d - y
print(cnt)


import heapq
H = []
n = int(input())
for i in list(map(int, input().split())):
	tot = tot + i if 'tot' in locals() or 'tot' in globals() else i
	tot -= (heapq.heappush(H, i) if tot >= 0 else heapq.heappushpop(H, i)) or 0
print(len(H))


import heapq
pq = []
heapq.heapify(pq)
n = int(input())
l = map(int, input().split())
h = ans = 0
for i in l:
	if h + i >= 0:
		h += i
		ans += 1
		heapq.heappush(pq, i)
	elif pq and heapq.nsmallest(1, pq)[0] < i:
		h -= heapq.heappop(pq)
		h += i
		heapq.heappush(pq, i)
print(ans)


import sys
import heapq
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
su = 0
h = []
ans = 0
for i in nums:
	su += i
	heapq.heappush(h, i)
	if su < 0:
		su -= heapq.heappop(h)
	else:
		ans += 1
print(ans)


import math
import heapq

def solve():
	n = int(input())
	arr = list(map(int, input().strip().split()))
	for i in range(n):
		if arr[i] >= 0:
			arr = arr[i:n + 1]
			n = len(arr)
			break
	heap = []
	S = 0
	ans = 0
	for i in range(n):
		if arr[i] < 0:
			heapq.heappush(heap, arr[i])
		S += arr[i]
		ans += 1
		while S < 0:
			a = heapq.heappop(heap)
			ans -= 1
			S -= a
	return ans
print(solve())


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split()]
	return res

def read_list_of_ints_zero():
	return [int(val) - 1 for val in input().rstrip('\n').split()]

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

def main():
	n = read_one_int()
	elements = read_list_of_ints()
	cur_sum = 0
	res = 0
	q = []
	heapq.heapify(q)
	for el in elements:
		if cur_sum + el >= 0:
			res += 1
			cur_sum += el
			if el < 0:
				heapq.heappush(q, el)
		elif not q:
			continue
		elif el > q[0]:
			popped = heapq.heappop(q)
			cur_sum -= popped
			cur_sum += el
			heapq.heappush(q, el)
	print(res)
main()


import heapq
n = int(input())
a = list(map(int, input().split()))
s = 0
h = []
for i in a:
	s += i
	heapq.heappush(h, i)
	if s < 0:
		s -= heapq.heappop(h)
print(len(h))


n = int(input())
a = list(map(lambda x: int(x), input().split()))
s = 0
ans = []
for i in range(n):
	if s + a[i] >= 0:
		s += a[i]
		ans.append(a[i])
		ans.sort()
	elif ans and ans[0] < a[i]:
		s += a[i] - ans[0]
		ans.pop(0)
		ans.append(a[i])
		ans.sort()
print(len(ans))


a = int(input())
arr = [int(arr) for arr in input().split()]
total = 0
count = 0
neg = []
for i in arr:
	total = total + i
	count = count + 1
	if i < 0:
		neg.append(i)
	if total < 0:
		total = total - min(neg)
		neg.remove(min(neg))
		count = count - 1
print(count)


input()
x = map(int, input().split())
m = 0
m1 = []
c = 0
for i in x:
	if m + i >= 0:
		if i < 0:
			m1 += [i]
	elif m1:
		if i > min(m1):
			m = m - min(m1)
			m1.remove(min(m1))
			m1.append(i)
			c -= 1
	if m + i >= 0:
		m += i
		c += 1
print(c)


n = int(input())
a = list(map(int, input().split()))
(arr, x, ans) = ([], 0, 0)
for i in range(n):
	if a[i] < 0:
		arr.append(a[i])
		arr = sorted(arr, reverse=True)
	x = x + a[i]
	if x < 0:
		x -= arr.pop()
	else:
		ans = ans + 1
print(ans)


import heapq
n = int(input())
a = list(map(int, input().split()))
ans = 0
sum_ = 0
lst = []
heapq.heapify(lst)
for i in range(n):
	if a[i] >= 0:
		sum_ += a[i]
		ans += 1
	elif sum_ + a[i] >= 0:
		sum_ += a[i]
		heapq.heappush(lst, a[i])
		ans += 1
	elif len(lst) != 0:
		min_ = heapq.heappop(lst)
		if min_ > a[i]:
			heapq.heappush(lst, min_)
		else:
			heapq.heappush(lst, a[i])
			sum_ += a[i] - min_
print(ans)


n = int(input())
A = list(map(int, input().split()))
import heapq
cur = 0
prev = []
cnt = 0
for x in A:
	if x < 0:
		if cur + x >= 0:
			cur += x
			heapq.heappush(prev, x)
			cnt += 1
		elif prev and prev[0] < x:
			cur += x - prev[0]
			heapq.heappop(prev)
			heapq.heappush(prev, x)
	else:
		cur += x
		cnt += 1
print(cnt)


import heapq as h
n = int(input())
l = list(map(int, input().split()))
k = 0
a = 0
z = []
for i in l:
	if i < 0:
		h.heappush(z, i)
	if k + i >= 0:
		k += i
		a += 1
	else:
		k -= h.heappop(z)
		k += i
print(a)


import heapq
n = int(input())
d = {}
a = list(map(int, input().split()))
one = 111
ans = []
twww00o = 2222
heapq.heapify(ans)
threee = 21
tot = 0
f54rth = 0
ct = 0
zkt = 54
flag = True
for i in a:
	th = 25
	tot += i
	z = 5
	ct += 1
	gh = 52
	if i < 0:
		ty = 10
		heapq.heappush(ans, i)
		k = 50
	while tot < 0:
		tr = 56
		t = heapq.heappop(ans)
		tot += abs(t)
		tg = 41
		ct -= 1
thu = 10
print(ct)


n = int(input())
arr = []
inp = input().split()
for i in inp:
	arr.append(int(i))
sum1 = 0
result = []
count = 0
import heapq
arr1 = []
for i in arr:
	sum1 += i
	count += 1
	if i < 0:
		heapq.heappush(arr1, i)
	if sum1 < 0:
		while sum1 < 0:
			s = heapq.heappop(arr1)
			sum1 -= s
			count -= 1
print(count)


import heapq

def question3():
	N = int(input())
	arr = list(map(int, input().split()))
	k1 = []
	heapq.heapify(k1)
	sum_upto = 0
	count = 0
	for i in range(N):
		sum_upto += arr[i]
		if arr[i] < 0:
			heapq.heappush(k1, arr[i])
		if sum_upto < 0:
			m1 = heapq.heappop(k1)
			sum_upto -= m1
		else:
			count += 1
	return count
remained_test_cases = 1
while remained_test_cases > 0:
	print(question3())
	remained_test_cases -= 1


import heapq as hp
n = int(input())
arr = list(map(int, input().split()))
s = 0
res = []
hp.heapify(res)
for i in arr:
	if i < 0:
		hp.heappush(res, i)
	s += i
	if s < 0:
		s -= hp.heappop(res)
		n -= 1
print(n)


n = int(input())
l = list(map(int, input().split()))
s = 0
c = 0
st = []
for i in range(n):
	s += l[i]
	c += 1
	if l[i] < 0:
		st.append(l[i])
		st = sorted(st, reverse=True)
	if s < 0:
		s -= st.pop()
		c -= 1
print(c)


n = int(input())
li = list(map(int, input().split()))
q = []
c = 0
v = 0
for i in range(0, n):
	v += li[i]
	c += 1
	if li[i] < 0:
		q.append(li[i])
		q.sort()
	if v < 0:
		v -= q[0]
		q.sort()
		q.pop(0)
		q.sort()
		c = c - 1
print(c)


import heapq
n = int(input())
arr = list(map(int, input().split()))
pq = []
curr = 0
count = 0
for ele in arr:
	if ele >= 0:
		curr += ele
		count += 1
	elif curr + ele >= 0:
		curr += ele
		heapq.heappush(pq, ele)
		count += 1
	elif pq and pq[0] < ele:
		curr -= heapq.heappop(pq)
		heapq.heappush(pq, ele)
		curr += ele
print(count)


n = int(input())
arr = list(map(int, input().split()))
heap = []
from heapq import heappop, heappush
cur = 0
for x in range(n):
	cur += arr[x]
	heappush(heap, arr[x])
	while cur < 0:
		k = heappop(heap)
		cur += -k
print(len(heap))


x = int(input())
a = list(map(int, input().split()))
b = []
s = 0
c = 0
for i in a:
	s = s + i
	c = c + 1
	if i < 0:
		b.append(i)
		b.sort()
	if s < 0:
		s = s - b[0]
		b.sort()
		b.pop(0)
		b.sort()
		c = c - 1
print(c)


from heapq import heapify, heappush, heappop
n = int(input())
arr = list(map(int, input().split()))
heap = []
heapify(heap)
health = 0
count = 0
for i in range(n):
	if health + arr[i] >= 0:
		health += arr[i]
		count += 1
		heappush(heap, arr[i])
	elif len(heap) > 0:
		val = heap[0]
		if val < 0 and val < arr[i]:
			heappop(heap)
			health += abs(val)
			if health + arr[i] >= 0:
				health += arr[i]
				count += 1
				heappush(heap, arr[i])
print(len(heap))


from heapq import *
from sys import stdin
input = stdin.readline
n = int(input())
lst = list(map(int, input().split()))
(hp, arr) = (0, [])
for i in lst:
	hp += i
	heappush(arr, i)
	if hp < 0:
		hp -= heappop(arr)
print(len(arr))


import sys
import heapq
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().rstrip().split(' ')))
B = [0]
heapq.heapify(B)
health = 0
for a in A:
	if health + a < 0:
		b = heapq.heappop(B)
		health -= b
		a = max(a, b)
	heapq.heappush(B, a)
	health += a
print(len(B) - 1)


import heapq
n = int(input())
l = list(map(int, input().split()))
hp = []
heapq.heapify(hp)
cnt = 0
cur = 0
for i in range(n):
	if l[i] >= 0:
		cur += l[i]
		cnt += 1
	elif cur + l[i] >= 0:
		cur += l[i]
		heapq.heappush(hp, l[i])
	elif len(hp) > 0:
		x = heapq.heappop(hp)
		if x < l[i]:
			cur += -x
			cur += l[i]
			heapq.heappush(hp, l[i])
		else:
			heapq.heappush(hp, x)
print(cnt + len(hp))


def solve(n, a):
	count = health = 0
	i = 0
	while i < len(a):
		health += a[i]
		count += 1
		if health < 0:
			min_dam = min(a[:i + 1])
			a.remove(min_dam)
			health -= min_dam
			count -= 1
			continue
		i += 1
	return count
n = int(input())
a = list(map(int, input().strip().split()))[:n]
print(solve(n, a))


from heapq import heapify, heappush, heappop
n = int(input())
arr = list(map(int, input().split()))
heap = []
heapify(heap)
_sum = 0
ans = 0
for i in range(n):
	_sum += arr[i]
	heappush(heap, arr[i])
	ans += 1
	while _sum < 0:
		pop = heappop(heap)
		_sum -= pop
		ans -= 1
print(ans)


from heapq import *
n = int(input())
l = list(map(int, input().split()))
q = []
heapify(q)
t = 0
res = 0
best = -99 ** 9
neg_top = 0
for i in l:
	if i >= 0:
		res += i
		t += 1
		best = max(best, t)
	elif res + i >= 0:
		heappush(q, i)
		res += i
		t += 1
		neg_top += i
		best = max(best, t)
	else:
		res += i
		heappush(q, i)
		t += 1
		neg_top += i
		while res < 0:
			h = heappop(q)
			res -= h
			t -= 1
			neg_top -= h
		best = max(best, t)
print(max(best, 0))


import bisect
I = input
IN = lambda x: map(int, x.split())
L = lambda x: list(IN(x))
n = int(I())
a = L(I())
j = 0
d = []
s = 0
for i in a:
	if i < 0:
		bisect.insort(d, -i)
	s += i
	if s < 0:
		s += d.pop()
		j += 1
print(n - j)


import heapq
n = int(input())
lis = list(map(int, input().split()))
l = list()
sum = 0
for i in lis:
	sum += i
	heapq.heappush(l, i)
	while sum < 0:
		sum -= heapq.heappop(l)
print(len(l))


import heapq

def func(i, num):
	count = 0
	total = 0
	heap = list()
	for i in range(n):
		count += a[i]
		total += 1
		heapq.heappush(heap, a[i])
		while count < 0:
			poison = heapq.heappop(heap)
			count -= poison
			total -= 1
	print(total)
n = int(input())
a = list(map(int, input().split()))
func(n - 1, 0)


import sys
import heapq
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().strip().split()))
ans = []
heapq.heapify(ans)
total = 0
for item in arr:
	total += item
	if total < 0:
		total -= heapq.heappushpop(ans, item)
	else:
		heapq.heappush(ans, item)
print(len(ans))


import heapq
n = int(input())
potion = list(map(int, input().split()))
(nowhp, ans) = (0, 0)
minheap = []
for i in range(n):
	if potion[i] >= 0:
		nowhp = nowhp + potion[i]
		ans = ans + 1
		continue
	elif nowhp + potion[i] >= 0:
		nowhp = nowhp + potion[i]
		ans = ans + 1
		heapq.heappush(minheap, potion[i])
		continue
	elif len(minheap) == 0 or potion[i] < heapq.nsmallest(1, minheap)[0]:
		continue
	else:
		nowhp = nowhp - heapq.nsmallest(1, minheap)[0] + potion[i]
		heapq.heappop(minheap)
		heapq.heappush(minheap, potion[i])
print(ans)


from heapq import *
n = int(input())
heap = []
(res, sumval) = (n, 0)
for i in map(int, input().split()):
	sumval += i
	heappush(heap, i)
	while sumval < 0:
		sumval -= heappop(heap)
		res -= 1
print(res)


import heapq
n = int(input())
a = [*map(int, input().split())]
(h, t) = ([], 0)
for i in a:
	t += i
	heapq.heappush(h, i)
	while t < 0:
		t -= heapq.heappop(h)
print(len(h))


import sys
import heapq
read = sys.stdin.readline

def run_case():
	n = int(read())
	ar = list(map(int, read().split()))
	heap = []
	i = 0
	s = 0
	res = 0
	while i < n:
		if ar[i] >= 0:
			s += ar[i]
			i += 1
			res += 1
		else:
			j = i
			while j < n and ar[j] < 0:
				j += 1
			tr = ar[i:j]
			i = j
			tr.sort(reverse=True)
			for t in tr:
				if s + t >= 0:
					s += t
					res += 1
					heapq.heappush(heap, t)
				elif len(heap) > 0 and heap[0] < t:
					s -= heap[0]
					res -= 1
					heapq.heappop(heap)
					s += t
					res += 1
					heapq.heappush(heap, t)
				else:
					break
	print(res)
run_case()


n = int(input())
potions = tuple(map(int, input().split()))
health = 0
res = 0
considered_harmful_potions = {}
most_harmful_potion = 0
for potion in potions:
	res += 1
	if potion < 0:
		if potion in considered_harmful_potions:
			considered_harmful_potions[potion] += 1
		else:
			considered_harmful_potions[potion] = 1
		most_harmful_potion = min(most_harmful_potion, potion)
	health += potion
	if health < 0:
		considered_harmful_potions[most_harmful_potion] -= 1
		health -= most_harmful_potion
		res -= 1
		if considered_harmful_potions[most_harmful_potion] == 0:
			del considered_harmful_potions[most_harmful_potion]
		most_harmful_potion = min(considered_harmful_potions.keys(), default=0)
print(res)


n = int(input())
A = list(map(int, input().split()))
sm = 0
cnt = 0
Neg = []
for i in range(n):
	if sm + A[i] >= 0:
		cnt += 1
		sm += A[i]
		if A[i] < 0:
			Neg.append(A[i])
	elif Neg:
		if A[i] > min(Neg):
			sm += A[i] - min(Neg)
			Neg.remove(min(Neg))
			Neg.append(A[i])
print(cnt)


import sys
import heapq

def main():
	size = int(sys.stdin.readline().split()[0])
	a = [int(x) for x in sys.stdin.readline().split()]
	heap = []
	tot = 0
	health = 0
	for num in a:
		if num >= 0:
			tot += 1
			health += num
		else:
			newHealth = health + num
			if newHealth >= 0:
				tot += 1
				health = newHealth
				heapq.heappush(heap, num)
			elif len(heap) == 0 or num < heap[0]:
				continue
			else:
				removed = heapq.heappop(heap)
				heapq.heappush(heap, num)
				health -= removed
				health += num
	print(tot)
main()


import heapq

def sol(A):
	li = []
	h = 0
	count = 0
	for i in range(len(A)):
		if h + A[i] >= 0:
			count += 1
			h += A[i]
			if A[i] < 0:
				heapq.heappush(li, A[i])
		elif li and li[0] < A[i]:
			h -= li[0]
			h += A[i]
			heapq.heapreplace(li, A[i])
	return count
x = int(input())
A = list(map(int, input().split()))
print(sol(A))


def solve(l):
	(c, s) = (0, 0)
	k = []
	for i in range(len(l)):
		if l[i] >= 0:
			s = s + l[i]
			c = c + 1
		else:
			k.append(l[i])
			s = s + l[i]
			c = c + 1
			while s < 0:
				k.sort()
				s = s - k[0]
				k.pop(0)
				c = c - 1
	return c
n = int(input())
l = list(map(int, input().split()))
print(solve(l))


n = int(input())
l = list(map(int, input().split()))
st = []
ct = 0
val = 0
for i in range(n):
	val += l[i]
	ct += 1
	if l[i] < 0:
		st.append(l[i])
		st = sorted(st, reverse=True)
	if val < 0:
		val -= st[-1]
		st.pop()
		ct = ct - 1
print(ct)


import heapq
n = int(input())
a = list(map(int, input().split()))
served = []
sum_ = 0
for i in range(n):
	heapq.heappush(served, a[i])
	sum_ += a[i]
	if sum_ < 0:
		sum_ -= heapq.heappop(served)
print(len(served))


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
import heapq
lens = RI()
arrs = RMI()
sum_now = 0
drop = []
heapq.heapify(drop)
for i in arrs:
	if i < 0:
		heapq.heappush(drop, i)
	sum_now += i
	if sum_now < 0:
		sum_now -= heapq.heappop(drop)
		lens -= 1
print(lens)


import heapq
n = int(input())
arr = list(map(int, input().split()))
H = []
tot = 0
for i in arr:
	tot += i
	heapq.heappush(H, i)
	while tot < 0:
		tot -= H[0]
		heapq.heappop(H)
print(len(H))


from heapq import *
n = int(input())
arr = list(map(int, input().split()))
h = []
heapify(h)
s = 0
for i in arr:
	s += i
	heappush(h, i)
	while s < 0:
		s -= h[0]
		heappop(h)
print(len(h))


from heapq import heappop, heappush, heapify
n = int(input())
a = list(map(int, input().split()))
heap = []
cnt = 0
ans = 0
for i in range(n):
	ans += a[i]
	cnt += 1
	if a[i] < 0:
		heappush(heap, a[i])
	if ans < 0:
		temp = -1 * heappop(heap)
		cnt -= 1
		ans += temp
print(cnt)


import heapq

def solve():
	heap = []
	health = 0
	potions = 0
	for i in range(N):
		if A[i] >= 0:
			health += A[i]
			potions += 1
		elif health + A[i] >= 0:
			heapq.heappush(heap, A[i])
			health += A[i]
			potions += 1
		elif heap and heap[0] <= A[i]:
			bad_potion = heapq.heappop(heap)
			heapq.heappush(heap, A[i])
			health += A[i] - bad_potion
			assert health >= 0
	return potions
N = int(input())
A = list(map(int, input().split()))
print(solve())


n = int(input())
list1 = list(map(int, input().split()))
s = 0
c = 0
b = []
for i in list1:
	s += i
	c += 1
	if i < 0:
		b.append(i)
		b.sort()
	if s < 0:
		s -= b[0]
		b.pop(0)
		c -= 1
print(c)


import heapq
n = int(input())
l = [int(x) for x in input().split()]
ans = 0
count = 0
x = []
heapq.heapify(x)
for i in range(n):
	ans += l[i]
	heapq.heappush(x, l[i])
	while ans < 0:
		ans = ans - heapq.heappop(x)
print(len(x))


import heapq
I = input
IN = lambda x: map(int, x.split())
L = lambda x: list(IN(x))
n = int(I())
a = L(I())
j = 0
d = []
s = 0
for i in a:
	s += i
	if s < 0:
		s -= heapq.heappushpop(d, i)
		j += 1
	elif i < 0:
		heapq.heappush(d, i)
print(n - j)


n = int(input())
potions = list(map(int, input().split(' ')))
res = []
s = 0
for i in range(n):
	s += potions[i]
	res.append(potions[i])
	if s < 0:
		m = min(res)
		res.remove(m)
		s += abs(m)
print(len(res))


import heapq
n = int(input())
arr = list(map(int, input().split()))
ans = 0
q = []
s = 0
for i in range(n):
	if s + arr[i] >= 0:
		ans += 1
		s += arr[i]
		if arr[i] < 0:
			heapq.heappush(q, arr[i])
	elif len(q) and q[0] < arr[i]:
		value = heapq.heappop(q)
		heapq.heappush(q, arr[i])
		s -= value
		s += arr[i]
print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
from heapq import heappush, heappop, heapify
n = int(input())
a = list(map(int, input().split()))
h = list()
heapify(h)
(s, r) = (0, 0)
for e in a:
	if s + e >= 0:
		(r, s) = (r + 1, s + e)
		if e < 0:
			heappush(h, e)
	elif len(h) and h[0] < e:
		s -= heappop(h)
		heappush(h, e)
		s += e
print(r)


from functools import lru_cache
from collections import deque, defaultdict
from heapq import heappop, heappush
I = lambda : map(int, input().split())

@lru_cache(None)
def dp(x, curr, cnt):
	if x == n:
		return cnt
	ans = 0
	for i in range(x, n):
		(op1, op2) = (0, 0)
		if A[i] + curr >= 0:
			op1 = dp(i + 1, curr + A[i], cnt + 1)
		op2 = dp(i + 1, curr, cnt)
		ans = max(ans, op1, op2)
	return ans

def solve(A):
	res = 0
	H = []
	(curr_sum, curr_len) = (0, 0)
	for a in A:
		curr_sum += a
		curr_len += 1
		heappush(H, a)
		while H and curr_sum < 0:
			x = heappop(H)
			curr_sum -= x
			curr_len -= 1
		res = max(res, curr_len)
	return res
t = 1
while t:
	t -= 1
	n = int(input())
	A = list(I())
	print(solve(A))


def poisons(n: int, dr: list):
	health = 0
	amount_pois = 0
	neg_pois = []
	for i in range(n):
		if dr[i] >= 0:
			amount_pois += 1
			health += dr[i]
			continue
		if health + dr[i] >= 0:
			amount_pois += 1
			health += dr[i]
			neg_pois.append(dr[i])
			continue
		if neg_pois:
			cur_min = min(neg_pois)
			if dr[i] > cur_min:
				health -= cur_min
				health += dr[i]
				neg_pois.remove(cur_min)
				neg_pois.append(dr[i])
	return amount_pois
n = int(input())
arr = list(map(int, input().split(' ')))
print(poisons(n, arr))


def put_into_list(num: int, arr: list):
	if not arr:
		arr.append(num)
		return
	for i in range(len(arr)):
		if arr[i] > num:
			arr.insert(i, num)
			return
	arr.append(num)

def poisons_simple(n: int, dr: list):
	health = 0
	amount_pois = 0
	neg_pois = []
	for i in range(n):
		if dr[i] >= 0:
			amount_pois += 1
			health += dr[i]
			continue
		if health + dr[i] >= 0:
			amount_pois += 1
			health += dr[i]
			put_into_list(dr[i], neg_pois)
			continue
		if neg_pois and dr[i] > neg_pois[0]:
			health -= neg_pois[0]
			health += dr[i]
			neg_pois.pop(0)
			put_into_list(dr[i], neg_pois)
	return amount_pois
n = int(input())
arr = list(map(int, input().split(' ')))
print(poisons_simple(n, arr))


def solve(n, a):
	count = health = 0
	arr = []
	for i in range(n):
		health += a[i]
		count += 1
		arr.append(a[i])
		if health < 0:
			min_dam = min(arr)
			arr.remove(min_dam)
			health -= min_dam
			count -= 1
	return count
n = int(input())
a = list(map(int, input().strip().split()))[:n]
print(solve(n, a))


n = int(input())
lis = list(map(int, input().split()))
ans = 0
arr = list()
import heapq
for i in lis:
	ans += i
	heapq.heappush(arr, i)
	while ans < 0:
		ans -= heapq.heappop(arr)
print(len(arr))


import sys
import math
import random
from queue import PriorityQueue

def solve(arr, n):
	count = 0
	pos = 0
	q = PriorityQueue()
	for i in arr:
		if i >= 0:
			count += 1
			pos += i
		elif pos + i >= 0:
			pos += i
			q.put(i)
			count += 1
		elif q.qsize() > 0 and q.queue[0] < i:
			val = q.get()
			q.put(i)
			pos = pos - val + i
	print(count)
n = int(input())
arr = list(map(int, input().split()))
solve(arr, n)


n = int(input())
l = list(map(int, input().split()))
s = 0
c = 0
a = []
k = 0
for i in range(n):
	s += l[i]
	if l[i] < 0:
		a.append(l[i])
		a.sort(reverse=True)
	if s < 0:
		x = a.pop()
		s = s - x
		k += 1
print(n - k)


n = int(input())
arr = list(map(int, input().split()))
dp = []
for i in arr:
	dp.append(i)
	if i >= 0:
		continue
	dp.sort()
	if sum(dp) < 0:
		dp.pop(0)
print(len(dp))


n = int(input())
lis = list(map(int, input().split()))
ans = 0
arr = list()
for i in lis:
	ans += i
	arr.append(i)
	arr.sort()
	while ans < 0:
		ans -= arr[0]
		arr.pop(0)
print(len(arr))


def potions(n):
	lst = [int(i) for i in input().split()]
	l = []
	for potion in lst:
		l.append(potion)
		if potion < 0 and sum(l) < 0:
			l = sorted(l)
			l.pop(0)
	print(len(l))
n = int(input())
potions(n)


import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ans = []
cnt = 0
for item in data:
	cnt += item
	heappush(ans, item)
	if cnt < 0:
		temp = heappop(ans)
		cnt -= temp
print(len(ans))


n = int(input())
drinkings = [int(item) for item in input().split(' ')]
health = 0
drinks = []
for i in range(n):
	health += drinkings[i]
	drinks.append(drinkings[i])
	if health < 0:
		Min = min(drinks)
		health -= Min
		drinks.remove(Min)
print(len(drinks))


n = int(input())
ls = list(map(int, input().split()))
(drk, ans, hp) = ([], 0, 0)
for i in ls:
	if i >= 0:
		(ans, hp) = (ans + 1, hp + i)
	elif hp + sum(drk) + i >= 0:
		drk.append(i)
	else:
		try:
			temp = min(drk)
		except ValueError:
			continue
		if temp < i:
			drk.remove(temp)
			drk.append(i)
print(ans + len(drk))


from queue import PriorityQueue
n = int(input())
a = list(map(int, input().split()))
Q = PriorityQueue()
s = 0
x = 0
for i in range(len(a)):
	x += 1
	Q.put(a[i])
	if s + a[i] >= 0:
		s += a[i]
	else:
		s += a[i]
		while not Q.empty():
			k = Q.get()
			s -= k
			x -= 1
			if s >= 0:
				break
print(x)


from heapq import heapify, heappush, heappop
n = int(input())
l = list(map(int, input().split()))
heap = []
heapify(heap)
ans = 0
a = 0
for i in range(n):
	a += l[i]
	ans += 1
	heappush(heap, l[i])
	while a < 0:
		a -= heappop(heap)
		ans -= 1
print(ans)


import heapq as h
n = input()
a = list(map(int, input().split()))
sum = 0
H = []
for x in a:
	sum += x
	h.heappush(H, x)
	if sum < 0:
		sum -= H[0]
		h.heappop(H)
print(len(H))


n = int(input())
s = count = 0
taken = []
ncount = 0
for i in list(map(int, input().split())):
	if i >= 0:
		count += 1
		ncount += 1
		s += i
	elif s + i >= 0:
		s += i
		count += 1
		taken.append(i)
	elif len(taken) > 0:
		v = min(taken)
		if s + i - v >= 0 and v < i:
			s += i - v
			taken.append(i)
			del taken[taken.index(v)]
		else:
			pass
print(ncount + len(taken))


n = int(input())
a = [int(x) for x in input().split()]
s = 0
k = 0
b = []
for i in range(0, n):
	s = s + a[i]
	k = k + 1
	if a[i] < 0:
		b.append(a[i])
	while s < 0:
		p = min(b)
		s = s - p
		k = k - 1
		b.remove(p)
print(k)


n = int(input())
a = list(map(int, input().split()))
import heapq
l = []
heapq.heapify(l)
ans = 0
s = 0
for i in range(0, len(a)):
	if a[i] < 0:
		heapq.heappush(l, a[i])
	s += a[i]
	if s < 0:
		ans += 1
		k = heapq.heappop(l)
		s -= k
print(len(a) - ans)


n = int(input())
a = list(map(int, input().split()))
S = []
for i in range(n):
	S.append(a[i])
	if sum(S) < 0:
		S.remove(min(S))
print(len(S))