Description

Tony2 的操作可以看作下冲和跳跃的组合。

称一个 $\text{Ultra}$ 为一段连续的操作，以下冲开头，然后跳跃和下冲交替，并以下冲结束。由于是 $\text{Ultra}$，所以至少要有一次跳跃。

小 C 每次可以将一个 $\text{Ultra}$ 变成 $\text{uLTRA}$，也就是将这个 $\text{Ultra}$ 的每个下冲变成跳跃，将每个跳跃变成下冲。

小 C 不喜欢 $\text{Ultra}$，所以想要使得下冲次数尽量少。

形式化题意

给你一个 $01$ 序列，你可以进行如下操作若干次（或零次）:

• 将序列中形如 $101\cdots01$ 的一个子串（即 $1(01)^k$，$k\ge 1$）替换成等长的 $010\cdots10$（即 $0(10)^k$）。

你要操作使得 $1$ 的个数尽可能少，输出最少的 $1$ 的个数。

Input Format

一行一个长度为 $n$（$n\le 10^6$） 的字符串表示这个 $01$ 序列。

Output Format

输出一个数表示最少的 $1$ 的个数。

1010011

3

Hint

样例 $1$ 解释：选中该串的前三个字符 $101$，对其操作后该串变为 $0100011$，仅包含 $3$ 个 $1$。容易证明这是最优的。