Дана строка \(s\) длины \(n\), состоящая из строчных букв английского алфавита.
Вы должны выбрать некоторое число \(k\) между \(0\) и \(n\). Затем вы выбираете некоторые \(k\) символов \(s\) и переставляете их как угодно. При этом позиции остальных символов \(n-k\) остаются неизменными. Эту операцию нужно выполнить ровно один раз.
Например, если \(s=\texttt{"andrea"}\), то можно выбрать \(k=4\) символов \(\texttt{"a_d_ea"}\) и переставить их в порядке \(\texttt{"d_e_aa"}\) так, чтобы после операции строка стала \(\texttt{"dneraa"}\).
Определите минимально возможное значение \(k\), выбрав которое можно отсортировать \(s\) в алфавитном порядке (то есть, чтобы после операции ее символы располагались в алфавитном порядке).
Выходные данные
Для каждого набора входных данных выведите минимальное значение \(k\), которое позволяет получить строку, отсортированную по алфавиту, с помощью операции, описанной выше.
Примечание
В первом наборе входных данных мы можем выбрать \(k=2\) символа \(\texttt{"_ol"}\) и переставить их как \(\texttt{"_lo"}\) (так что результирующая строка будет \(\texttt{"llo"}\)). Невозможно отсортировать строку, выбирая строго менее \(2\) символов.
Во втором наборе входных данных одним из возможных способов сортировки \(s\) является рассмотрение \(k=6\) символов \(\texttt{"_o__force_"}\) и перестановка их как \(\texttt{"_c__efoor_"}\) (так что результирующая строка будет \(\texttt{"ccdeefoors"}\)). Можно показать, что невозможно отсортировать строку, выбирая строго меньше \(6\) символов.
В третьем наборе входных данных, строка \(s\) уже отсортирована (поэтому мы можем выбрать \(k=0\) символов).
В четвертом наборе входных данных мы можем выбрать все \(k=4\) символов \(\texttt{"dcba"}\) и перевернуть всю строку (так что результирующая строка будет \(\texttt{"abcd"}\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
lol
10
codeforces
5
aaaaa
4
dcba
|
2
6
0
4
|