Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.

During all his career Hideo has produced n games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.

More formally, you are given an array s_1, s_2, ..., s_{n} of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.

Besides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV.


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 100).

The second line contains n space-separated integer numbers s_1, s_2, ..., s_{n} (0 ≤ s_{i} ≤ 1). 0 corresponds to an unsuccessful game, 1 — to a successful one.


-----Output-----

Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.


-----Examples-----
Input
4
1 1 0 1

Output
3

Input
6
0 1 0 0 1 0

Output
4

Input
1
0

Output
1

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = list(map(int, input().split()))

ans = 0
x0 = 0
x1 = 0
for i in range(n):
    if s[i] == 1:
        x1 = max(x0, x1) + 1
    else:
        x0 = x0 + 1
    ans = max(x0, x1)
print(ans)


length = int(input())
array = list(map(int, input().split()))

count = []
total = 0

for k in range(length):
    if array[length - 1 - k] == 1:
        total += 1
    count.append(total)
count.reverse()

total = 0
maximum = 0
for k in range(length):
    if array[k] == 0:
        total += 1

    maximum = max(maximum, total + count[k])

print(maximum)


n = int(input())
a = [int(i) for i in input().split()]
ans = sum(a)
for i in range(len(a) - 1, - 1, -1):
    ans = min(ans, (len(a) - i - sum(a[i:])) + sum(a[:i]))
print(len(a) - ans)


n = int(input())
s = list(map(int, input().split()))
max_games = 0
for i in range(n+1):
    max_games = max(max_games, s[:i].count(0) + s[i:].count(1))
print(max_games)


n = int(input())
arr = list(map(int, input().split()))
pref1 = [0]
for i in arr:
    pref1.append(pref1[-1] + i)
suf0 = [0]
for i in arr[::-1]:
    suf0.append(suf0[-1] + (i + 1) % 2)
ans = []
for i in range(n + 1):
    ans.append(n - (suf0[::-1][i] + pref1[i]))
print(max(ans))

n =  int(input())
data = list(map(int, input().split()))
data2 = [0] * n
data2[0] = data[0]
for i in range(1, n):
    if data[i]:
        data2[i] = data2[i - 1] + 1
    else:
        data2[i] = data2[i - 1]
data2 = [0] + data2
ma = -2
for i in range(n + 1):
    ma = max(ma, data2[-1] - data2[i] + i - data2[i])
print(ma)



def solve(s):
    '''
    >>> solve([1, 1, 0, 1])
    3
    >>> solve([0, 1, 0, 0, 1, 0])
    4
    >>> solve([0])
    1
    '''
    zeroes = accum(s, 0)
    ones = list(reversed(accum(reversed(s), 1)))
    return max(x + y for x, y in zip(zeroes, ones))


def accum(lst, value):
    counts = [0]
    for el in lst:
        if el == value:
            counts.append(counts[-1] + 1)
        else:
            counts.append(counts[-1])
    return counts


def main():
    n = input()
    s = list(map(int, input().split()))
    print(solve(s))


def __starting_point():
    main()

__starting_point()

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

n = int(input())
s = read_ints()
to_rem = n if sum(s) else 0
for i in range(n):
	to_rem = min(to_rem, s[:i].count(1) + (s[i:].count(0) if sum(s[i:]) else 0))

print(n - to_rem)

n = int(input())
games = list(map(int, input().split()))

strike = [0] * n

for i in range(n):
	strike[i] = 1
	for j in range(i):
		if games[j] <= games[i]:
			strike[i] = max(strike[i], strike[j] + 1)

# print(strike)
print(max(strike))


n = int(input())
nums = list(map(int, input().split()))

right = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
    right[i] = nums[i]
    if i < n - 1:
        right[i] += right[i + 1]
        
left = [0 for i in range(n)]
for i in range(n):
    left[i] = nums[i]
    if i > 0:
        left[i] += left[i - 1]
        
res = 0
for i in range(-1, n):
    count = 0
    if i >= 0:
        count = i + 1 - left[i]
    if i + 1 < n:
        count += right[i + 1]
    res = max(res, count)

print(res)

n = int(input())

def it():
  A = list(map(int,input().split()))
  A.reverse()

  c1 = 0
  r0 = len(A) - sum(A)
  yield r0

  for a in A:
    if a == 1:
      c1 += 1
      yield c1 + r0
    else:
      r0 -= 1

print(max(it()))






INF = 10 ** 9 + 7


def cutoff(games, pos):
    leave = 0

    for i, g in enumerate(games):
        if i < pos:
            if g == 0:
                leave += 1
        else:
            if g == 1:
                leave += 1

    return leave


def main():
    n = int(input())

    games = [int(x) for x in input().split()]

    max_leave = -INF

    for i in range(n+1):
        max_leave = max(max_leave, cutoff(games, i))

    print(max_leave)


def __starting_point():
    main()


__starting_point()

n = int(input())
a = [int(i) for i in input().split()]
answer = [0] * n
answer[0] = 1

for i in range(1, n):
    if a[i] == 1:
        answer[i] = max(answer) + 1
    else:
        temp_max = 0
        for j in range(i):
            if a[j] == 0 and answer[j] > temp_max:
                temp_max = answer[j]
        answer[i] = temp_max + 1
        
print(max(answer))

import math

n = int(input())
a = list(map(int, input().split()))

z2 = a.count(0)
o2 = n - z2
z1 = 0
o1 = 0

res = z1 + o2
i = 0
while i < n:
	z2 -= (1-a[i])
	z1 += (1-a[i])
	o2 -= (a[i])
	o1 += (a[i])
	res = max(res, z1+o2)
	i+=1
print(res)

a=int(input())
b=[int(i) for i in input().split()]
c=b.copy()
ans=0
for i in range(a):
    if b[i]==1:
        ans+=(b[i:].count(1))
        break
    ans+=1
ans1=0
for i in range(a):
    if b[i]==1:
        ans1=max(ans1,b[:i].count(0)+b[i:a].count(1))
print(max(ans,ans1,b.count(0),b.count(1)))

        


n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(a.count(0) + 1):
    zc = 0
    for j in range(n):
        if a[j] == 0:
            zc += 1
        if zc == i:
            break
    ans = max(ans, i + a[j:].count(1))
print(ans)

import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
m = 0
d = Counter(a)
for i in range(d[0]+1):
    j = 0
    k = 0
    while k != i:
        if a[j] == 0:
            k += 1
        j += 1
    while j < n:
        if a[j] == 1:
            k += 1
        j += 1
    m = max(m,k)
print(m)


from sys import stdout
from random import randint 
from math import *
import re


n = int(input())
s = input().replace(' ', '')

ones = s.count("1")
zeros = 0
mx = 0
for c in s:
    zeros += c == '0'
    if zeros + ones > mx: mx = zeros + ones
    ones -= c == '1'

print(mx)


n = int(input())
a = list(map(int, input().split()))
l = [a[i+1:].count(0)+a[:i].count(1) for i in range(n)]
print(n - min(l))

n = int(input())
a = list(map(int, input().split()))
p = [0] * n
p[0]= a[0]
for i in range(1, n):
    p[i] = p[i - 1] + a[i]
ans = min(n, n - p[n - 1])
for i in range(n):
    l = p[i]
    r = (n - i - 1) - (p[n - 1] - p[i])
    ans = min(ans, l + r)
print(n - ans)


n = int(input())
val = list(map(int, input().split()))
k = 0
for i in range(n + 1):
    k = max(k, i - sum(val[:i]) + sum(val[i:]))
print(k)

n = int(input())

l = list(map(int, input().split()))

max_games = [1 for i in range(n)]

if n > 1:
    if l[1] == 0:
        if l[0] == 1:
            max_games[1] = 1
        else:
            max_games[1] = 2
    else:
        max_games[1] = 2

t_max = max(max_games)

if n > 2:
    for i in range(2, n):
        if l[i] == 0:
            j = i - 1
            while (j >= 0):
                if l[j] == 0:
                    max_games[i] = max_games[j] + 1
                    t_max = max([t_max, max_games[i]])
                    break
                j -= 1
        else:
            max_games[i] = t_max + 1
            t_max += 1



print(t_max)


n = int(input())
arr = list(map(int, input().split()))

ans = arr.count(0)
for i in range(1, n + 1):
    one = 0
    ind = -1
    j = n - 1
    for j in range(n -1, -1, -1):
        if one == i:
            ind = j
            break
        if arr[j] == 1:
            one += 1
    else:
        if one == i:
            ind = j
        else:
            break
    ans = max(ans, i + arr[:ind + 1].count(0))
print(ans)


KoKoKo = int
kudaxKudax = input
kukareku = max
kokokokoko = print
kudkudax = range




kokoko = KoKoKo(kudaxKudax())
ko = [KoKoKo(x) for x in kudaxKudax().split()]
KO = KOKOKO = 0
for kok in kudkudax(kokoko - 1, -1, -1):
    KO += ko[kok]
    KOKOKO = kukareku(KOKOKO, KO + ko[:kok + 1].count(0))
kokokokoko(KOKOKO)

n = int(input())
p = list(map(int, input().split()))
ind_z = []
ind_o = []
for i in range(n):
    if p[i] == 0:
        ind_z.append(i)
    else:
        ind_o.append(i)
z = [0] * len(ind_z)
o = [0] * len(ind_o)
for i in range(len(z)):
    z[i] = i + 1
    for j in range(ind_z[i], n):
        if p[j] == 1:
            z[i] += 1
for i in range(len(o)):
    o[i] = len(o) - i 
    for j in range(ind_o[i] - 1, -1, -1):
        if p[j] == 0:
            o[i] += 1 
z = [0] + z
o = [0] + o
print(max(max(o), max(z)))