题目描述

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

输入格式

第一行是一个整数 $n$，表示队伍的长度。

第二行是 $n$ 个整数，每个整数为 0 或 1，表示每个选手的类型。

输出格式

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

样例

4
0 1 0 1

2

6
1 0 1 0 1 0

7

样例解释

• 样例 1：初始兴奋值总和为 $1$（第二位大神看到了一个菜鸟）。将第四个位置的菜鸟换成大神后，序列变为 0 1 0 0，兴奋值总和变为 $2$（第三位大神看到 $1$ 个菜鸟，第四位大神看到 $2$ 个菜鸟）。
• 样例 2：初始兴奋值总和为 $6$。将第二个位置的大神换成菜鸟后，序列变为 1 1 1 0 1 0，兴奋值总和变为 $7$（第四位大神看到 $3$ 个菜鸟，第六位大神看到 $4$ 个菜鸟）。

数据范围与提示

• 对于 $30\%$ 的数据：$1 \le n \le 100$；
• 对于 $60\%$ 的数据：$1 \le n \le 1000$；
• 对于 $100\%$ 的数据：$1 \le n \le 10^5$。