Problem Description

For a binary sequence $\{a_n\}$, find the smallest $k$ such that there exists a set $\{(l_k, r_k)\}$ satisfying the following conditions:

• For all $i \in [1, n]$, $a_i = 1$ if and only if there exists $j \in [1, k]$ where $i \in [l_j, r_j]$.

It can be proven that there is only one set $\{(l_k, r_k)\}$ that satisfies the condition.

A binary sequence $\{a_n\}$ is considered good if and only if for all $i \in [1, k)$, $r_i - l_i < r_{i+1} - l_{i+1}$.

In simpler terms, a binary sequence is good if the lengths of the longest consecutive segments of 1s increase strictly from left to right.

Given a sequence $\{a_n\}$, you can perform the following operation any number of times (or not at all):

• Choose $i, j$ ($i \neq j$), and swap $a_i$ and $a_j$.

Determine the minimum number of operations required to transform $\{a_n\}$ into a good sequence.

Input Format

A single line containing a binary sequence $\{a_n\}$ of length $n$ ($n \leq 800$).

Output Format

A single number representing the answer.

Sample Input and Output

Sample Input #1

01101

Sample Output #1

1

Sample Input #2

01011

Sample Output #2

0

见题面 Input 部分

见题面 Output 部分