Давайте определим циклический сдвиг некоторой строки \(s\) как преобразование из \(s_1 s_2 \dots s_{n-1} s_{n}\) в \(s_{n} s_1 s_2 \dots s_{n-1}\). Другими словами, вы берете один последний символ \(s_n\) и помещаете его перед первым символом, сдвигая все остальные символы вправо.
Вам задана бинарная строка \(s\) (строка, состоящая только из символов 0 и/или 1).
За одну операцию вы можете выбрать любую подстроку \(s_l s_{l+1} \dots s_r\) (\(1 \le l < r \le |s|\)) и выполнить ее циклический сдвиг. Стоимость такой операции равна \(r - l + 1\) (или же длине выбранной подстроки).
Вы можете выполнять данную операцию любое количество раз. Какова минимальная суммарная стоимость, чтобы отсортировать строку \(s\) в порядке неубывания?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную суммарную стоимость, чтобы сделать строку отсортированной, используя вышеуказанную операцию произвольное количество раз.
Примечание
В первом наборе входных данных вы можете выбрать всю строку и выполнить циклический сдвиг: 10 \(\rightarrow\) 01. Длина подстроки равна \(2\), поэтому стоимость составляет \(2\).
Во втором наборе строка уже отсортирована, поэтому вам не нужно выполнять никаких операций.
В третьем наборе одной из оптимальных стратегий является следующая:
- выбрать подстроку \([1, 3]\): 11000 \(\rightarrow\) 01100;
- выбрать подстроку \([2, 4]\): 01100 \(\rightarrow\) 00110;
- выбрать подстроку \([3, 5]\): 00110 \(\rightarrow\) 00011.
Общая стоимость равна
\(3 + 3 + 3 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10
0000
11000
101011
01101001
|
2
0
9
5
11
|