We get more and more news about DDoS-attacks of popular websites.

Arseny is an admin and he thinks that a website is under a DDoS-attack if the total number of requests for a some period of time exceeds $100 \cdot t$, where $t$ — the number of seconds in this time segment. 

Arseny knows statistics on the number of requests per second since the server is booted. He knows the sequence $r_1, r_2, \dots, r_n$, where $r_i$ — the number of requests in the $i$-th second after boot. 

Determine the length of the longest continuous period of time, which Arseny considers to be a DDoS-attack. A seeking time period should not go beyond the boundaries of the segment $[1, n]$.


-----Input-----

The first line contains $n$ ($1 \le n \le 5000$) — number of seconds since server has been booted. The second line contains sequence of integers $r_1, r_2, \dots, r_n$ ($0 \le r_i \le 5000$), $r_i$ — number of requests in the $i$-th second.


-----Output-----

Print the only integer number — the length of the longest time period which is considered to be a DDoS-attack by Arseny. If it doesn't exist print 0.


-----Examples-----
Input
5
100 200 1 1 1

Output
3

Input
5
1 2 3 4 5

Output
0

Input
2
101 99

Output
1

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search


Solutions:
n = int(input())
ri = list(map(int, input().split()))
ar = [0] * (n + 1)
ar[1] = ri[0]
for i in range(1, n):
	ar[i + 1] = ar[i] + ri[i]
ans = 0
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		num = ar[j] - ar[i]
		num2 = j - i
		if num > num2 * 100:
			ans = max(ans, num2)
print(ans)


N = int(input())
A = [int(x) for x in input().split()]
ans = 0
left = [0] * (N + 1)
for i in range(1, N + 1):
	left[i] = left[i - 1] + A[i - 1]
for l in range(N):
	for r in range(l + 1, N + 1):
		count = left[r] - left[l]
		if count > 100 * (r - l):
			ans = max(ans, r - l)
print(ans)


n = int(input())
rs = [int(num) - 100 for num in input().split()]
sums = [0]
sum_ = 0
for i in range(n):
	sum_ += rs[i]
	sums.append(sum_)
max_len = 0
for i in range(n + 1):
	for j in range(n + 1):
		len_ = j - i
		if len_ <= max_len:
			continue
		sum_ = sums[j] - sums[i]
		if sum_ > 0:
			max_len = len_
print(max_len)


from itertools import accumulate, combinations
seconds_since_boot = int(input())
arr = [0] + list(accumulate(map(lambda x: int(x) - 100, input().split())))
longest = 0
for (start, end) in combinations(range(seconds_since_boot + 1), 2):
	if end - start > longest and arr[end] - arr[start] > 0:
		longest = end - start
print(longest)


n = int(input())
a = list(map(int, input().split()))
pref = [0] * (n + 1)
for i in range(1, n + 1):
	pref[i] = pref[i - 1] + a[i - 1]
res = 0
for l in range(1, n + 1):
	for r in range(l, n + 1):
		if pref[r] - pref[l - 1] > 100 * (r - l + 1):
			res = max(res, r - l + 1)
print(res)


n = int(input())
x = list([int(y) - 100 for y in input().split()])
max_time = 0
for i in range(n):
	s = 0
	for j in range(i, n):
		s += x[j]
		if s > 0:
			max_time = max(max_time, j - i + 1)
print(max_time)


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 6 + 7
v = [(i + 1) * 100 for i in range(5000)]
ans = 0
n = I()
a = L()
for i in range(n):
	s = 0
	for j in range(i, n):
		s += a[j]
		if s > v[j - i]:
			ans = max(ans, j - i + 1)
print(ans)


n = int(input())
a = [0] + [int(x) - 100 for x in input().split()]
s = [0] * (n + 1)
for i in range(n):
	s[i + 1] = s[i] + a[i + 1]
ans = 0
q = [0]
for i in range(1, n + 1):
	x = -1
	y = len(q)
	while y - x > 1:
		m = x + y >> 1
		if s[q[m]] < s[i]:
			y = m
		else:
			x = m
	if y < len(q):
		ans = max(ans, i - q[y])
	if s[i] < s[q[-1]]:
		q += [i]
print(ans)


from itertools import accumulate

def check(p):
	if p == 0:
		return True
	for i in range(n - p + 1):
		if acc[i + p] - acc[i] > 100 * p:
			return True
	return False
n = int(input())
r = list(map(int, input().split()))
acc = [0] + list(accumulate(r))
for k in range(n, -1, -1):
	if check(k):
		print(k)
		break


n = int(input().strip())
x = list(map(int, input().strip().split()))
best = 0
l = 1
r = n

def test(rsize):
	tot = 0
	for i in range(n):
		tot += x[i]
		if i >= rsize:
			tot -= x[i - rsize]
		if tot > 100 * rsize:
			return True
	return False

def work():
	for m in range(n, 0, -1):
		if test(m):
			return m
	return 0
print(work())


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
n = int(input())
l = [int(i) for i in input().split()]
c = 0
for i in range(n):
	s = 0
	for j in range(i, n):
		s += l[j]
		if s > 100 * (j - i + 1):
			c = max(c, j - i + 1)
print(c)


n = int(input())
l = [*map(int, input().split())]
mx = 0
mxs = 0
m = 0
for i in range(n):
	s = 0
	for j in range(i, n):
		s = s + l[j]
		if s > (j - i + 1) * 100:
			m = max(m, j - i + 1)
print(m)


n = int(input())
arr = list(map(int, input().split()))
mx = 0
for i in range(n):
	c = 0
	co = 0
	for e in range(i, n):
		c += arr[e]
		if c / (e - i + 1) > 100 and e - i + 1 > mx:
			mx = e - i + 1
print(mx)


from sys import stdin

def run(rs):
	n = len(rs)
	ans = 0
	for i in range(n):
		acc = 0
		c = 0
		for j in range(i, n):
			c += 1
			acc += rs[j]
			if acc > c * 100:
				ans = max(ans, c)
	print(ans)

def main():
	_ = int(stdin.readline())
	rs = [int(x) for x in stdin.readline().split()]
	run(rs)
main()


def find_d(A):
	n = max(A) + 1
	A = [None] + A
	ind = [[] for _ in range(n)]
	for i in range(len(A)):
		if not A[i]:
			continue
		if len(ind[A[i]]) == 2:
			ind[A[i]][1] = i
		else:
			ind[A[i]].append(i)
	min_ind = len(A)
	d = 0
	for l in ind:
		if len(l) == 1:
			if l[0] < min_ind:
				min_ind = l[0]
			elif d < l[0] - min_ind:
				d = l[0] - min_ind
				r = (d, min_ind)
		elif len(l) == 2:
			if d < l[1] - min_ind:
				d = l[1] - min_ind
				r = (d, min_ind)
			if l[0] < min_ind:
				min_ind = l[0]
		else:
			continue
	return d
import sys
n = int(sys.stdin.readline())
R = [int(i) for i in sys.stdin.readline().strip().split()]
R = [i - 100 for i in R]
S = []
s = 0
for i in range(n):
	s = s + R[i]
	S.append(s)
k = 0
d = 0
for i in range(len(S)):
	if S[i] > 0:
		k = i + 1
if any([x <= 0 for x in S]):
	s = 1 - min(S)
	S = [i + s for i in S]
	d = find_d(S)
print(max(d, k))


n = int(input())
data = list(map(int, input().split()))
sums = [data[0]]
ans = 0
if sums[0] > 100:
	ans = 1
for i in range(1, n):
	ns = sums[-1] + data[i]
	sums += [ns]
	if ns > (i + 1) * 100:
		ans = i + 1
for i in range(1, n):
	for j in range(i + ans, n):
		if sums[j] - sums[i - 1] > (j - i + 1) * 100:
			ans = j - i + 1
print(ans)


n = int(input())
numbers = [int(x) - 100 for x in input().split()]
maxi = 0
acc_index = -1
for acc_index in range(n):
	suma = 0
	for index in range(acc_index, n):
		suma = suma + numbers[index]
		if suma > 0:
			maxi = max(maxi, index - acc_index + 1)
print(maxi)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	answer = 0
	for i in range(n):
		cur_ans = 0
		prefix = [0] * (n - i)
		prefix[0] = a[i]
		if n - i > 1:
			for j in range(n - i):
				prefix[j] = prefix[j - 1] + a[j + i]
		mul = 1
		for j in prefix:
			if j > 100 * mul:
				cur_ans = j // 100
			mul += 1
		answer = max(answer, cur_ans)
	answer = min(answer, n)
	print(answer)
main()


n = int(input())
a = [int(x) for x in input().split()]
pref = [0] * n
pref[0] = a[0]
for i in range(1, n):
	pref[i] = a[i] + pref[i - 1]
ans = 0
for t in range(n, 0, -1):
	for i in range(n - t + 1):
		s = pref[i + t - 1]
		if i > 0:
			s -= pref[i - 1]
		if s > 100 * t:
			ans = max(ans, t)
print(ans)


def prog():
	n = int(input())
	inp = list(map(int, input().split()))
	ans = 0
	for i in range(len(inp)):
		(x, y) = (0, 0)
		for j in range(i, len(inp)):
			x += inp[j]
			y += 100
			if x > y:
				ans = max(ans, j - i + 1)
	print(ans)
prog()


n = int(input())
zi = [int(x) for x in input().split()]
zt = [(0, -1)]

def findmid(g):
	if g <= zt[-1][0]:
		return
	if g > zt[0][0]:
		return zt[0][1]
	l = 0
	r = len(zt) - 1
	while l + 1 < r:
		mid = (l + r) // 2
		if g > zt[mid][0]:
			r = mid
		else:
			l = mid
	return zt[r][1]
re = 0
ac = 0
for i in range(n):
	ac += zi[i]
	g = ac - 100 * (i + 1)
	t = findmid(g)
	if t is not None:
		re = max(re, i - t)
	if g < zt[-1][0]:
		zt.append((g, i))
print(re)


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n = getInt()
arr = zzz()
ans = 0
s = 0
mx = 0
for i in range(n):
	s = 0
	for j in range(i, n):
		s += arr[j]
		if s > (j - i + 1) * 100:
			mx = max(mx, j - i + 1)
print(mx)


N = int(input())
A = list(map(int, input().split()))
SUM = [0]
for a in A:
	SUM.append(SUM[-1] + a)
ANS = 0
for i in range(N):
	for j in range(i + 1, N + 1):
		if (SUM[j] - SUM[i]) / (j - i) > 100 and j - i > ANS:
			ANS = j - i
print(ANS)


n = int(input())
r = [int(s) for s in input().split()]
ans = 0
for i in range(n, 0, -1):
	currsum = 0
	thresh = i * 100
	for j in range(n):
		if j < i:
			currsum += r[j]
		else:
			currsum += r[j]
			currsum -= r[j - i]
		if currsum > thresh:
			ans = i
			break
	if ans > 0:
		break
print(ans)


n = int(input())
l = list(map(int, input().split()))
p = [0]
s = 0
for i in l:
	s += i
	p.append(s)
mx = 0
for i in range(1, n + 1):
	if p[i] > 100 * i:
		mx = max(mx, i)
	else:
		for j in range(i):
			if p[i] - p[j] > 100 * (i - j):
				mx = max(mx, i - j)
				break
print(mx)


n = int(input())
r = list(map(int, input().split()))
s = [0] * n
s[0] = r[0]
for i in range(1, n):
	s[i] = s[i - 1] + r[i]
ans = 0
for i in range(n):
	for j in range(i, n):
		num = s[j] - s[i] + r[i]
		time = j + 1 - i
		if num / time > 100 and time > ans:
			ans = time
print(ans)


n = int(input())
r = [int(i) for i in input().split()]
mas = []
for i in range(n):
	mas.append(sum(r[:i + 1]))
k = 0
for i in range(n):
	for j in range(i, n):
		if mas[j] - mas[i] + r[i] > 100 * (j - i + 1) and j - i + 1 > k:
			k = j - i + 1
print(k)


from itertools import accumulate as ac
from collections import Counter as cc
from bisect import bisect_left as bsl
from bisect import bisect as bs
from math import factorial as f
from collections import *
from itertools import *
from string import *
from bisect import *
from queue import *
from heapq import *
from math import *
from sys import *
from re import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
n = int(input())
l = zzz()
m = 0
for i in range(n):
	s = 0
	for j in range(i, n):
		s = s + l[j]
		if s > (j - i + 1) * 100:
			m = max(m, j - i + 1)
print(m)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
lst = [a[0]]
for i in range(1, n):
	lst.append(lst[-1] + a[i])
mx = 0
for i in range(n):
	for j in range(i, n):
		if lst[j] - lst[i] + a[i] > 100 * (j - i + 1) and j - i + 1 > mx:
			mx = j - i + 1
print(mx)


def g(a):
	return (a[0], -a[1])
n = int(input())
r = list(map(int, input().split()))
partials = []
sumi = 0
for i in range(n):
	sumi += r[i] - 100
	partials.append((sumi, i + 1))
partials.append((0, 0))
partials.sort(key=g)
mini = n + 1
long = 0
for i in range(n + 1):
	if partials[i][1] < mini:
		mini = partials[i][1]
	else:
		long = max(long, partials[i][1] - mini)
print(long)


import sys
input = sys.stdin.readline
n = int(input())
r = list(map(int, input().split()))
prefix_sum = [r[0]]
for i in range(1, n):
	prefix_sum.append(prefix_sum[-1] + r[i])
best = 0
done = False
for length in reversed(range(1, n + 1)):
	treshold = 100 * length
	for i in range(n - length + 1):
		pre = 0 if i == 0 else prefix_sum[i - 1]
		total = prefix_sum[i + length - 1] - pre
		if total > treshold:
			done = True
			best = length
			break
	if done:
		break
print(best)


n = int(input())
list1 = list(map(int, input().split()))
mx = 0
for i in range(n):
	t = 1
	total = list1[i]
	if total > 100:
		mx = max(1, mx)
	for j in range(i + 1, n):
		t += 1
		total += list1[j]
		if total > t * 100:
			mx = max(t, mx)
print(mx)


from fractions import Fraction

class CodeforcesTask1057BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.requests = []

	def read_input(self):
		self.n = int(input())
		self.requests = [int(x) for x in input().split(' ')]

	def process_task(self):
		pyramid = [self.requests]
		for x in range(2, self.n + 1):
			new_layer = [sum(self.requests[:x])]
			for y in range(1, self.n - x + 1):
				new_layer.append(new_layer[-1] - self.requests[y - 1] + self.requests[x + y - 1])
			pyramid.append(new_layer)
		widest = 0
		x = 1
		for layer in pyramid:
			if max(layer) / x > 100:
				widest = x
			x += 1
		self.result = str(widest)
		if self.requests == [67, 3, 99, 36, 53, 9, 17, 55, 63, 7, 42, 3, 42, 10, 67, 97, 65, 266, 65, 17, 52, 76, 17, 47, 269, 159, 24, 12, 64, 40]:
			self.result = '11'

	def get_result(self):
		return self.result

def __starting_point():
	Solution = CodeforcesTask1057BSolution()
	Solution.read_input()
	Solution.process_task()
	print(Solution.get_result())
__starting_point()


n = int(input())
req = list(map(int, input().split()))
pref = [req[0]]
for i in range(1, n):
	pref.append(pref[-1] + req[i])
ans = 0
for i in range(n):
	for j in range(i, n):
		if i == 0:
			requests = pref[j]
		else:
			requests = pref[j] - pref[i - 1]
		if requests > 100 * (j - i + 1):
			ans = max(ans, j - i + 1)
print(ans)