Matches

Bajtek is playing with matches. Each match has a head on one end, coated with a substance that makes it easy to ignite. Bajtek laid the matches in a straight line, side by side, so that every end of a match touches an end of another match, except for the two outermost matches, each of which touches another match at only one end.

An example arrangement of the matches.

Bajtek wants to light the leftmost match so that all of the matches burn. He lights the first match with a lighter, so he can always ignite it no matter which way it faces. Between two neighboring matches, however, the fire spreads only if at least one of the two matches has its head at the point where they touch. Find the minimum number of matches that must be flipped so that, after the first match is lit, every match burns.

The first line contains a single integer $n$ ($1 \le n \le 1\,000\,000$), the number of matches. The second line describes their orientation with $n$ integers $x_1, x_2, \dots, x_n$, where $x_i$ is the orientation of the $i$-th match: $0$ if its head is on the left and $1$ if its head is on the right.

Print a single integer: the minimum number of matches that must be flipped.