Coin Flipping Game

You are given a row of coins. Each coin shows either heads or tails. Heads is represented by 1 and tails by 0.

An operation is defined as choosing some number k (where 1 ≤ k ≤ n, with n being the total number of coins) and flipping the first k coins simultaneously (i.e. each coin in that prefix turns from 0 to 1, or from 1 to 0).

Your task is to determine the minimum number of such operations required to make all coins show heads (1).

Note: If a coin is flipped an even number of times its state remains the same, and if flipped an odd number of times its state is inverted.

The optimal strategy turns out to be equivalent to counting the number of transitions between adjacent coins from left to right and adding one if the last coin is tails. In other words, if the coin string is represented by s, then the answer is:

\(\text{answer} = \left( \sum_{i=0}^{n-2} [s_i \neq s_{i+1}] \right) + \begin{cases}1, & \text{if } s_{n-1} = 0, \\ 0, & \text{if } s_{n-1} = 1.\end{cases}\)

inputFormat

The input consists of a single line containing a non-empty string of characters 0 and 1 representing the coins in order from left to right. There are no spaces in the input.

outputFormat

Output a single integer — the minimum number of operations required to flip all coins to heads (1).

sample

0

1