Дана строка \(s\) длины \(n\). За одну операцию можно выбрать лексикографически наибольшую\(^\dagger\) подпоследовательность строки \(s\) и циклически сдвинуть её вправо\(^\ddagger\).
Ваша задача — вычислить минимальное количество операций, необходимых для того, чтобы \(s\) стала отсортированной, или сообщить, что она никогда не достигнет отсортированного состояния.
\(^\dagger\)Строка \(a\) лексикографически меньше строки \(b\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(a\) является префиксом \(b\), но \(a \ne b\);
- В первой позиции, где \(a\) и \(b\) отличаются, строка \(a\) имеет букву, которая встречается раньше в алфавите, чем соответствующая буква в \(b\).
\(^\ddagger\)Циклическим сдвигом строки \(t_1t_2\ldots t_m\) вправо называется строка \(t_mt_1\ldots t_{m-1}\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, необходимых для того, чтобы сделать \(s\) отсортированной, или \(-1\), если это невозможно.
Примечание
В первом наборе входных данных строка \(s\) уже отсортирована, поэтому нам не нужны операции.
Во втором наборе входных данных, сделав одну операцию, мы выберем cb и циклически сдвинем её. Теперь строка \(s\) становится равной abc, которая отсортирована.
В третьем наборе входных данных \(s\) не может быть отсортирована.
В четвертом наборе входных данных мы сделаем следующие операции:
- Лексикографически наибольшая подпоследовательность равна zca. Тогда \(s\) становится равной abzc.
- Лексикографически наибольшая подпоследовательность равна zc. Тогда \(s\) становится равной abcz. Строка становится отсортированной.
Таким образом, нам нужно \(2\) операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz
|
0
1
-1
2
6
0
|