题目描述

一群信息学选手排队，每个选手都只能看到他左边的所有选手。选手分为两种：大神和菜鸟。在本题中，用1代表菜鸟，用0代表大神。大神每看到一个菜鸟就会获得1点兴奋值（因为可以炸鱼）。如果你可以更换其中一个选手，把菜鸟换成大神，或者把大神换成菜鸟，也可以选择不更换。请问所有大神的兴奋值的总和最多是多少？

输入格式

第一行是一个整数n，代表队伍的长度 第二行是n个整数，只会有0和1

输出格式

输出一个整数，代表大神们兴奋值总和的最大值

样例输入1

4
0 1 0 1

样例输出1

2

样例输入2

6
1 0 1 0 1 0

样例输出2

7

样例解释

样例1解释

初始队伍为[0,1,0,1]，不更换任何选手时的兴奋值计算：

• 第1个选手（0，大神）：左边无选手，兴奋值0；
• 第2个选手（1，菜鸟）：非大神，无兴奋值；
• 第3个选手（0，大神）：左边有1个菜鸟（第2个），兴奋值1；
• 第4个选手（1，菜鸟）：非大神，无兴奋值； 此时总和为1。
  若将第4个选手的1换成0，队伍变为[0,1,0,0]：
• 第1个0：兴奋值0；
• 第2个1：无兴奋值；
• 第3个0：左边1个菜鸟，兴奋值1；
• 第4个0：左边1个菜鸟，兴奋值1； 总和为2，这是能得到的最大值，因此输出2。

样例2解释

初始队伍为[1,0,1,0,1,0]，不更换任何选手时的兴奋值计算：

• 第1个选手（1，菜鸟）：无兴奋值；
• 第2个选手（0，大神）：左边1个菜鸟，兴奋值1；
• 第3个选手（1，菜鸟）：无兴奋值；
• 第4个选手（0，大神）：左边2个菜鸟（第1、3个），兴奋值2；
• 第5个选手（1，菜鸟）：无兴奋值；
• 第6个选手（0，大神）：左边3个菜鸟（第1、3、5个），兴奋值3； 此时总和为1+2+3=6。
  若将第5个选手的1换成0，队伍变为[1,0,1,0,0,0]：
• 第2个0：左边1个菜鸟，兴奋值1；
• 第4个0：左边2个菜鸟（第1、3个），兴奋值2；
• 第5个0：左边2个菜鸟（第1、3个），兴奋值2；
• 第6个0：左边2个菜鸟（第1、3个），兴奋值2； 总和为1+2+2+2=7，这是能得到的最大值，因此输出7。

数据约定

对于 30% 的测试数据，有 1 ≤ n ≤ 100；
对于 60% 的测试数据，有 1 ≤ n ≤ 1000；
对于 100% 的测试数据，有 1 ≤ n ≤ 10^5。