Leading the Fluttershies, we arrived at the Sweet Apple Acres.
"Only to see her lower her body, two front hooves pressed against the ground, waist twisted, legs kicked, two powerful hind legs striking the trunk like bullets. With a muffled sound accompanied by the rustling of leaves, the entire tree's apples fell into the basket without missing a beat," whispered one of the Fluttershies.
"Fluttershy, how do you have so many?" Would I talk like that, I had only just risen to this doubt when I was interrupted by Applejack's voice coming from far away.
"There's nothing wrong with that," another Fluttershy said coolly, as the apples in Applejack's basket inexplicably flew up one by one.
Strange, why would some of me even have magic? I hurriedly helped Applejack gather the apples and stopped the actions of Fluttershies.
Formally, the act of stopping can be abstracted into the following problem:
Given a string $$$s$$$ of length $$$n$$$ consisting only of 0 and 1. I can perform the following operation any number of times: choose a substring of $$$s$$$ and a positive number $$$k$$$, then cyclically shift the substring $$$k$$$ positions to the left.
String $$$a$$$ is a substring of string $$$b$$$ if and only if $$$a$$$ can be obtained by deleting some characters from the beginning and end of $$$b$$$ (which can be none or all of them).
Assume there is a string $$$s=s_0s_1s_2\dots s_{m-2}s_{m-1}$$$, shifting it $$$k$$$ positions to the left will result in $$$s_{k'}s_{k'+1}\dots s_{m-1}s_{0}s_{1}\dots s_{k'-2}s_{k'-1}$$$, where $$$k'=k\bmod m$$$.
A string $$$s$$$ consisting only of 0 and 1 is sorted if and only if for all $$$1 \leq i \lt n$$$, $$$s_i \leq s_{i+1}$$$. Here, characters are compared based on their numerical values.
For example, shifting the substring 1011 of string 0101100 two positions to the left results in 0111000.
I need to find the minimum number of operations required to make $$$s$$$ sorted.
One line containing a string $$$s$$$ consisting only of 0 and 1, where $$$|s|$$$ denotes the length of $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$).
Output one line containing an integer, representing the minimum number of operations required to make $$$s$$$ sorted.
01010101
3
11001010001
3
In the first example, one feasible set of minimal operations is 01010101 $$$\rightarrow$$$ 00110101 $$$\rightarrow$$$ 00011101 $$$\rightarrow$$$ 00001111, where we shift the substring $$$[1,2]$$$ by $$$1$$$ position, the substring $$$[2,4]$$$ by $$$2$$$ positions, and the substring $$$[3,6]$$$ by $$$3$$$ positions. Please note that string indices start from $$$0$$$.
In the second example, one feasible set of minimal operations is 1100101001 $$$\rightarrow$$$ 0011101001 $$$\rightarrow$$$ 0011100011 $$$\rightarrow$$$ 0000011111, where we shift the substring $$$[0,3]$$$ by $$$2$$$ positions, the substring $$$[6,8]$$$ by $$$1$$$ position, and the substring $$$[2,7]$$$ by $$$3$$$ positions.
| Название |
|---|


