Iahub got bored, so he invented a game to be played on paper. 

He writes n integers a_1, a_2, ..., a_{n}. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values a_{k} for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.

The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a_1, a_2, ..., a_{n}. It is guaranteed that each of those n values is either 0 or 1.


-----Output-----

Print an integer — the maximal number of 1s that can be obtained after exactly one move. 


-----Examples-----
Input
5
1 0 0 1 0

Output
4

Input
4
1 0 0 1

Output
4



-----Note-----

In the first case, flip the segment from 2 to 5 (i = 2, j = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].

In the second case, flipping only the second and the third element (i = 2, j = 3) will turn all numbers into 1.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = input().replace(' ', '')
ans = 0
for i in range(n):
    for j in range(i, n):
        s = a[i:j + 1]
        ans = max(ans, s.count('0') + (a[:i] + a[j + 1:]).count('1'))
print(ans)



n = int(input())
l = list(map(int,input().split()))
m = -1
for i in range(n):
    for j in range(i,n):
        c = 0
        for ind in range(n):
            if i <= ind <= j:
                if l[ind] == 0:
                    c += 1
            else:
                if l[ind] == 1:
                    c += 1
        m = max(m,c)
print(m)

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

res = 0
for i in range(n):
    for j in range(i, n):
        b = a[:]
        for u in range(i, j+1):
            if b[u]:
                b[u] = 0
            else:
                b[u] = 1
        res = max(res, b.count(1))
print(res)

n=int(input())
A = list(map(int, input().split()))
B=A[:]
max=0
for i in range(n):
    for k in range(n):
        for z in range(i,k+1):
            if A[z]==1:
                A[z]=0
            else:
                A[z]=1
            if A.count(1)>max:
                max=A.count(1)
        A=B[:]
print(max)

n = int(input())
numbers  = list(map(int, input().split()))
count_1 = numbers.count(1)
Max = 0
for i in range(n):
    for j in range(i, n):
        Max = max(Max, count_1 + (j - i + 1) - 2 * sum(numbers[i:j + 1]))
print(Max)

n = int(input())
a = list (map (int, input().split()))
one_count = 0
lcs,cur = 0,0
for i in a:
  if i == 1:
    one_count += 1
    cur = max (0, cur-1)
  else:
    cur += 1
    lcs = max (lcs, cur)
print((one_count+lcs) if one_count != n else one_count-1)


n = int(input())

s=input().split()

for i in range(n):
    s[i]=int(s[i])



ans=sum(s)
if(len(s)==1):
    print(1-s[0])
elif(s.count(0)==len(s)):
    print(len(s))
elif(s.count(1)==len(s)):
    print(sum(s)-1)
else:
    r=0
    if(s[0]==0):
       s=[1]+s
       r=1
    L=[0]
    for i in range(1,n+r):
        if(s[i]!=s[i-1]):
            L.append(i)
    L.append(n+r)
    m=len(L)
    maxx=0
    for i in range(2,m,2):
        ans=sum(s)-r+L[i]-L[i-1]
        e=ans
        for j in range(i+2,m,2):
            ans=ans+L[j]-L[j-1]-(L[j-1]-L[j-2])
            if(ans>e):
                e=ans            
        if(e>maxx):
            maxx=e
    print(maxx)
    
    


n = int(input())
input_str = input()
m = tmp = i = 0
while i<2*n-1:
    if input_str[i]=='0':
        tmp+=1
    elif tmp>0:
        tmp-=1
    m = max(m, tmp)
    i+=2
if m==0:
    print(n-1)
else:
    print(input_str.count('1')+m)


n = int(input())
a = list(map(int, input().split(' ')))
s = 0
for i in range(0, n):
    for j in range(i, n):
        t = 0
        for k in range(0, n):
            t += a[k] ^ (k >= i and k <= j)
        s = max(s, t)
print(s)

import sys
# f = open('input', 'rt')
f = sys.stdin
n = int(f.readline())
a = []
for s in f.readline().split():
    a += [int(s)]
m = 0
for i in range(n):
    for j in range(i, n):
        s1 = sum(a[:i])
        s2 = sum(1 - t for t in a[i:j + 1])
        s3 = sum(a[j + 1:])
        m = max(m, s1 + s2 + s3)
print(m)

import sys
# f = open('input', 'rt')
f = sys.stdin
n = int(f.readline())
a = list(map(int, f.readline().split()))
print(max(sum(a[:i]) + sum(1 - t for t in a[i:j + 1]) + sum(a[j + 1:]) for i in range(n) for j in range(i, n)))

n = int(input())
bs = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i, n):
        ans = max(ans, sum(bs) + j - i + 1 - 2 * sum(bs[i: j + 1]))
print(ans)


n = int(input())
numbers = list(map(int, input().split()))
cnt = numbers.count(1)
MAX = 0

for i in range(n):
    for j in range(i, n):
        MAX = max(MAX, cnt + (j - i + 1) - 2 * sum(numbers[i:j+1]))
print (MAX)


n = int(input())
I = list(map(int, input().split()))
d = []
for val in I:
    d.append(val)
res = 0;
for i in range (0, n):
    for j in range (i, n):
        cnt = 0;
        for k in range (0, n):
            if k >= i and k <= j:
                cnt = cnt + 1 - d[k];
            else:
                cnt = cnt + d[k];
        if cnt > res:
            res = cnt;
print (res)

            


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

sol = 0
inv = [1, 0]

for i in range(0, n):
    for j in range(i, n):
        val = 0
        for k in range(0, n):
            if k < i or k > j: val += a[k]
            else: val += inv[a[k]]

        sol = max(sol, val)
            
print(sol)


import sys

def main():
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    total_sum = sum(a)
    if n == 1:
        print(1 - sum(a))
        return
    max_sum = total_sum
    for i in range(n):
        for j in range(i+1, n+1):
            new_sum = total_sum + j-i-2*sum(a[i:j])
            if new_sum > max_sum:
                max_sum = new_sum
    if max_sum == total_sum:
        max_sum -= 1
    print(max_sum)
	
def __starting_point():
    return(main())

__starting_point()

n = int(input())
a = list(map(int, input().split()))
ans, s = 0, a.count(1)
for i in range (n):
    for j in range (i + 1, n + 1):
        tmp = a[i:j].count(0) - a[i:j].count(1)
        if s + tmp > ans: ans = s + tmp
print(ans)

n = int(input()) 
vec = list(map(int, input().split(' ')))
s = [0]
cnt = 0
ans = 0
for x in vec:
    s.append(x + s[-1])
    if x == 1:
        cnt = cnt + 1
for i in range(1, n + 1):
    for j in range(1, i + 1):
        one = s[i] - s[j - 1]
        tot = i - j + 1
        ans = max(ans, cnt - one + tot - one)
print(ans)



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


ans=-n
for i in range(n):
    for j in range(i,n):
        u=j-i+1-2*a[i:j+1].count(1)
        if u>ans:
            ans=u
           #print(i,j,ans)

print(a.count(1)+ans)


input()
a = list(map(int, input().split()))
b = [0] + [0 for i in a]
c = [0] + [0 for i in a]
d = -1000
for i in range(len(a)):
  b[i + 1] = b[i] + a[i]
  c[i + 1] = c[i] + 1 - a[i]
for i in range(len(a)):
  for j in range(i + 1):
    d = max(d, c[i + 1] - c[j] - b[i + 1] + b[j])
print(d + b[-1])

import sys
my_file = sys.stdin
#my_file = open("input.txt", "r")
n = int(my_file.readline().strip())
a = [int(i) for i in my_file.readline().strip().split()]
max = 0
for end in range(n, -1, -1):
    for begin in range(end):
        s = sum(a[:begin]+[i^1 for i in a[begin:end+1]]+a[end:])
        if s > max:
            max = s
print(max)

n, t = int(input()), list(map(int, input().split()))
k = t.count(1)
p = [0] * n

s, m = 0, 0
for i in range(0, n):
    s += [-1, 1][t[i]]
    t[i] = s
    if s > m: m = s 
    p[i] = m

m, s = t[-1], p[-1] - t[-1]
for i in range(2, n + 1):
    m = min(t[-i], m)
    d = p[-i] - m
    if s < d: s = d
    
print(k + s - (k == n))

n, t = int(input()), list(map(int, input().split()))
k = t.count(1)
t = [1 - 2 * i for i in t]

m, s = -1, 0

for i in range(n):
    s = max(s, 0)
    s += t[i]
    m = max(m, s)

print(k + m)


def number_of_ones_if_flipped(l, from_index, to_index):
    counter = 0
    for i in range(len(l)):
        if not (from_index <= i and i <= to_index):
            if l[i] == 1:
                counter += 1
        else:
            if l[i] == 0:
                counter += 1
    return counter

def all_possible_flips(l):
    maximum = -1 * float("inf")

    for i in range(0, len(l)):
        for j in range(i, len(l)):
            if number_of_ones_if_flipped(l, i, j) > maximum:
                maximum = number_of_ones_if_flipped(l, i, j)

    return maximum
    
                
            
    

def main():
    first_line = input()
    first_line = first_line.split()
    
    n = int(first_line[0])

    l = input()
    l = l.split()
    for i in range(len(l)):
        l[i] = int(l[i])
    
    
    print(all_possible_flips(l))
    
main()



n = int(input())
a = list(map(int, input().split()))
mx = 0
for i in range(n):
    for j in range(i+1, n+1):
        t = sum(a[0:i]) + a[i:j].count(0) + sum(a[j:n])
        if t > mx: mx = t

print(mx)