题目描述

小z在探险中发现了一排 $n$ 个古老的宝箱，从左到右依次编号为 $1 \sim n$。每个宝箱可能是空的也可能藏着珍贵的宝藏。

小z可以选择一段连续的宝箱区间 $[l,r]$（满足 $l \le r$），然后一次性打开 $l \sim r$ 号的所有宝箱。他想用最少的操作获得所有宝藏，请问他最少需要连续打开几个宝箱？

注意：小z有可能一个宝箱都不需要打开（当没有宝藏时）。

• 对于 $30$% 的数据，$1 \le n \le 100$
• 对于 $60$% 的数据，$1 \le n \le 2000$
• 对于 $100$% 的数据，$1 \le n \le 10^5$，$0 \le a_i \le 1$

输入格式

第一行一个整数 $n$，表示宝箱的数量。

第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$：

• 若 $a_i = 1$，表示第 $i$ 个宝箱中有宝藏
• 若 $a_i = 0$，表示第 $i$ 个宝箱是空的

输出格式

输出一行一个整数 ，表示小z最少需要连续打开的宝箱数量。

6
0 0 1 1 0 1

4

5
0 0 0 1 0

1

提示

样例 $1$ 解释，打开区间 $[3,6]$（即第 3,4,5,6 号宝箱）可以一次性获得所有宝藏。这个区间包含 4 个宝箱，且不存在更小的区间能包含所有宝藏。