Дана строка $$$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}$$$.