Iahub 觉得无聊,所以他发明了一种在纸上玩的游戏。
他写了 n 个整数 a1, a2, ..., an。这些整数中的每一个都可以是 0 或 1。他只能执行一次移动:他选择两个索引 i 和 j (1 ≤ i ≤ j ≤ n) 并翻转其位置在 [i, j] 范围内(即 i ≤ k ≤ j)的所有值 ak。翻转 x 的值意味着应用 x = 1 - x 运算。
游戏的目标是在恰好走完一步后获得最大数量的 1。编写一个程序来解决Iahub的小游戏。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100)。输入的第二行有 n 个整数:a1, a2, ..., an。保证这 n 个值中的每一个都是 0 或 1。
输出
打印一个整数 — 一次移动后可获得的 1 的最大数量。
示例
输入 #1
5 1 0 0 1 0
输出 #1
4
输入 #2
4 1 0 0 1
输出 #2
4
注意
在第一种情况下,将段从 2 翻转到 5 (i = 2, j = 5)。翻转改变了顺序,它变成:[1 1 1 0 1]。所以,它包含四个。没有办法让整个序列等于[1 1 1 1 1]。
在第二种情况下,仅翻转第二个和第三个元素(i = 2,j = 3)会将所有数字变为 1。