Dyzio is a friend of Jasiek and also likes riddles. Here is the riddle Dyzio brought to Jasiek:

Jasiek, here is a string that needs to be cut into smaller pieces. I won't tell you directly how to do it, but look at this sequence of zeros (0) and ones (1). A one at the beginning means the string must be cut in half. However, if the first digit were a zero, it would be the only digit in the sequence and would mean you don't have to do anything anymore - I want the string to remain whole. If you do have to cut the string, then after the first one, I have written what to do with the left piece (applying the same rules as for the whole string), and then I have written what to do with the right piece (always sticking to the same notation rules). You must always cut the left piece first, and only then can you proceed to the right one. Now, cut it and tell me the minimum number of cuts required to obtain the shortest piece.

Unfortunately, Jasiek's mother hides the scissors from him, but luckily a computer was at hand, and Jasiek quickly wrote a program simulating the cutting of the string. Can you write such a program too?

Write a program that:

• reads (from standard input) the description of how to cut the string,
• calculates the minimum number of cuts required to obtain the (first) shortest piece,
• prints the result (to standard output).

Input

The first line of input contains an integer $n$ ($1 \le n \le 20\,000$). The second line of input contains exactly one binary string (a sequence of zeros and ones without spaces between them) of length $n$ - the description of the string cutting method provided by Dyzio.

Output

Your program should print (to standard output) only one line containing a single integer, equal to the minimum number of cuts required to obtain the shortest piece.

Examples

Input 1

9
110011000

Output 1

4