P9517 drink


There are $n$ bottles in front of you, numbered from left to right as $1 \sim n$. Each bottle may be empty or may contain water. You can choose a pair $l, r (l \le r)$, and then drink up all the water in bottles $l \sim r$. You want to drink all the remaining water on the table in one go. What is the minimum number of bottles you need to pick up? It is possible that you do not need to pick up any bottle.

The first line contains an integer $n$. The second line contains $n$ integers. The $i$-th integer is $1$ if the $i$-th bottle contains water, and $0$ if the $i$-th bottle is empty.

Output one integer $k$, representing the minimum number of bottles to pick up.

**Sample Explanation** In Sample $1$, picking up bottle $4$ is enough. In total, $1$ bottle is picked up. In Sample $2$, picking up bottles $3 \sim 6$ allows you to drink all the water. In total, $4$ bottles are picked up. **Constraints** For $30\%$ of the testdata, it is guaranteed that $n \le 100$. For $60\%$ of the testdata, it is guaranteed that $n \le 2000$. For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$, and $0 \le a_i \le 1$. Translated by ChatGPT 5