Megumin is trying to deactivate a security system! The security system is composed of ~N~ different switches, and is only fully deactivated when all of the switches are off. Let's define flipping a switch as changing it from on to off, or vice versa. Megumin has thought of the ingenious idea of
exploding the whole thing flipping the switches with her staff to avoid detection! However, given her position, she can only use her staff to flip a prefix of the switches (switches ~1~ to ~k~, ~1 \le k \le N~) in one click. Can you help her figure out the minimum number of clicks needed to fully deactivate the system without using explosion?
The first line will contain an integer ~N~ (~1 \le N \le 10^6~).
The next line will contain a string of ~N~ characters
1, representing the states of the switches from ~1~ to ~N~ (
0 is off,
1 is on).
Output the minimum number of clicks required to fully deactivate the system.
Explanation for Sample Output
Megumin can use her staff to flip the first 3 switches, changing the states to
Then she can flip all the switches, changing the states to
Finally, she can use her staff to flip the first switch, changing the states to
0000 and fully deactiviating the system.