Problem Description

For a $01$ sequence $\{a_n\}$, find the minimum $k$ such that there exists a set $\{(l_k,r_k)\}$ that satisfies the following condition.

• $\forall i\in[1,n]$, $a_i=1$ if and only if $\exist j\in[1,k]$, $i\in[l_j,r_j]$.

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

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

In simple terms, a $01$ sequence is good if and only if the lengths of the maximal consecutive segments of $1$ formed from left to right are strictly increasing.

Given the sequence $\{a_n\}$, you may perform the following operation any number of times (or do nothing):

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

Find the minimum number of operations needed to make $\{a_n\}$ a good sequence.

Input Format

One line containing a $01$ sequence $\{a_n\}$ of length $n$ ($n\leq 800$).

Output Format

One line containing one number, which is the answer.

01101

1

01011

0

Hint

Translated by ChatGPT 5