Problem Description

$ N $ cells are arranged in a row. Some of the cells may contain tokens. You are given a string $ s $ consisting of 0 and 1. The $ i $-th character of $ s $ is 1 if the $ i $-th cell (from the left) contains one token, otherwise it does not contain a token.

Snuke wants to perform the following operation as many times as possible. In each operation, three consecutive cells are chosen. Let the cells be $ X, Y, Z $ from left to right. To perform the operation, both $ X $ and $ Z $ must contain tokens, and $ Y $ must not contain a token. Then, Snuke removes these two tokens and places one new token in $ Y $.

When performing the operations in the optimal way, how many operations can Snuke perform?

Input Format

The input is given from the standard input in the following format:

$ N $ $ s $

Output Format

Print the answer.

Sample Input and Output

Sample Input #1

7
1010101

Sample Output #1

2

Sample Input #2

50
10101000010011011110001001111110000101010111100110

Sample Output #2

10

Notes/Hints

Constraints

• $1 \leq N \leq 500,000$
• $ |s| = N $
• Each character in $ s $ is either 0 or 1.

Sample Explanation 1

For example, the operations can be performed twice as follows: - Perform the operation on the last three cells. The string representing tokens becomes 1010010. - Perform the operation on the first three cells. The string representing tokens becomes 0100010. Note that the order of operations is important. For example, if you choose the middle three cells first, you cannot perform any more operations.

见题面 Input 部分

见题面 Output 部分