Background

Tony2 likes playing a certain two-character game. One day, he showed his $\text{Ultra}$ in front of Xiao C.

But Xiao C does not know how to $\text{Ultra}$, so he went to Tutu-jiang.

Then Tutu failed

So while Tony2 was not around, Xiao C secretly swapped his jump key and down-dash key. (

Problem Description

Tony2’s actions can be seen as a combination of down-dash and jump.

An $\text{Ultra}$ is defined as a continuous segment of actions: it starts with a down-dash, then jump and down-dash alternate, and it ends with a down-dash. Since it is an $\text{Ultra}$, it must contain at least one jump.

Each time, Xiao C can turn an $\text{Ultra}$ into $\text{uLTRA}$, that is, within this $\text{Ultra}$, change every down-dash into a jump, and change every jump into a down-dash.

Xiao C does not like $\text{Ultra}$, so he wants the number of down-dashes to be as small as possible.

Formal statement

You are given a $01$ sequence. You may perform the following operation any number of times (possibly zero times):

• Replace a substring of the form $101\cdots01$ (i.e., $1(01)^k$, $k\ge 1$) with an equal-length substring $010\cdots10$ (i.e., $0(10)^k$).

Your goal is to make the number of $1$’s as small as possible. Output the minimum possible number of $1$’s.

Input Format

One line contains a string of length $n$ ($n\le 10^6$) representing this $01$ sequence.

Output Format

Output one number, the minimum possible number of $1$’s.

1010011

3

Hint

Explanation for sample $1$: choose the first three characters $101$. After applying the operation, the string becomes $0100011$, which contains only $3$ ones. It is easy to prove that this is optimal.

Translated by ChatGPT 5