Вам дана двоичная строка \(s\), состоящая только из символов 0 и/или 1.
Вы можете выполнить несколько (возможно, ноль) операций над строкой. Каждая операция имеет один из двух типов:
- выбрать два соседних элемента строки и поменять их местами. Такой вид операции стоит \(10^{12}\) монет;
- выбрать любой элемент строки и удалить его. Такой вид операции стоит \(10^{12}+1\) монет.
Ваша задача — определить минимальное количество монет, необходимое для сортировки строки \(s\) в порядке неубывания (т. е. преобразовать \(s\) таким образом, что \(s_1 \le s_2 \le \dots \le s_m\), где \(m\) — длина строки после применения всех операций). Пустая строка также считается отсортированной в порядке неубывания.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество монет, необходимое для сортировки строки \(s\) в порядке неубывания.
Примечание
В первом примере необходимо удалить \(1\)-й элемент, чтобы строка стала равной 00.
Во втором примере строка уже отсортирована.
В третьем примере необходимо поменять местами \(2\)-й и \(3\)-й элементы, чтобы строка стала равной 0011.
В четвертом примере необходимо поменять местами \(3\)-й и \(4\)-й элементы, чтобы строка стала равной 00011101, а затем удалить \(7\)-й элемент, чтобы строка стала равной 0001111.
В пятом примере необходимо удалить \(1\)-й элемент, чтобы строка стала равной 001101, а затем удалить \(5\)-й элемент, чтобы строка стала равной 00111.
В шестом примере строка уже отсортирована.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
100
0
0101
00101101
1001101
11111
|
1000000000001
0
1000000000000
2000000000001
2000000000002
0
|