Background

Problem Description

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.

Input Format

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 Format

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

5
0 0 0 1 0

1

6
0 0 1 1 0 1

4

Hint

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