题目描述

对于 $01$ 序列 $\{a_n\}$，找到最小的 $k$ 满足存在一组 $\{(l_k,r_k)\}$使得以下条件成立。

• $\forall i\in[1,n]$，$a_i=1$ 当且仅当 $\exist j\in[1,k]$，$i\in[l_j,r_j]$。

可以证明满足条件的 $\{(l_k,r_k)\}$ 仅有一个。

一个 $01$ 序列 $\{a_n\}$ 是好的当且仅当 $\forall i\in[1,k)$，$r_i-l_i<r_{i+1}-l_{i+1}$。

简单来说，一个 $01$ 序列是好的当且仅当从左到右形成的极长 $1$ 段长度严格递增。

给定序列 $\{a_n\}$，你可以进行如下操作若干次（或不进行操作）：

• 选择 $i,j$$(i\ne j)$，交换 $a_i,a_j$。

试求最小的操作次数使得 $\{a_n\}$ 变成一个好的序列。

输入格式

一行一个长为 $n$（$n\leq 800$） 的 $01$ 序列 $\{a_n\}$。

输出格式

一行一个数字，表示答案。

01101

1

01011

0