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

Difficulty: interview

Starter code:

Solutions:
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())
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)

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

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)

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, combinations
seconds_since_boot = int(input())
arr = [0] + list(accumulate([int(x) - 100 for x in input().split()]))
longest = 0
for start, end in combinations(list(range(seconds_since_boot + 1)), 2):
    if end-start > longest and arr[end] - arr[start] > 0:
        longest = end - start
print(longest)


# B. DDoS
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())
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)

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())
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())
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=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)
    
    


'''input
5
100 200 1 1 1
5
1 2 3 4 5
2
101 99

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


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)


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]
            else:
                if 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))

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)
def __starting_point():
    main()
__starting_point()

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

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 11/20/18


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⋅𝑡, where 𝑡 — 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 𝑟1,𝑟2,…,𝑟𝑛, where 𝑟𝑖 — the number of requests in the 𝑖-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,𝑛].

Input
The first line contains 𝑛 (1≤𝑛≤5000) — number of seconds since server has been booted.
The second line contains sequence of integers 𝑟1,𝑟2,…,𝑟𝑛 (0≤𝑟𝑖≤5000), 𝑟𝑖 — number of requests in the 𝑖-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.

"""



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

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

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:
            #print(x, len(layer), layer)
            if max(layer) / x > 100:
                #print(max(layer), x, 100, max(layer) / 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()