Codeforces Round 915 (Div. 2) |
---|
Закончено |
Дана строка $$$s$$$ длины $$$n$$$. За одну операцию можно выбрать лексикографически наибольшую$$$^\dagger$$$ подпоследовательность строки $$$s$$$ и циклически сдвинуть её вправо$$$^\ddagger$$$.
Ваша задача — вычислить минимальное количество операций, необходимых для того, чтобы $$$s$$$ стала отсортированной, или сообщить, что она никогда не достигнет отсортированного состояния.
$$$^\dagger$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:
$$$^\ddagger$$$Циклическим сдвигом строки $$$t_1t_2\ldots t_m$$$ вправо называется строка $$$t_mt_1\ldots t_{m-1}$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки $$$s$$$.
Вторая строка каждого набора входных данных содержит одну строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, необходимых для того, чтобы сделать $$$s$$$ отсортированной, или $$$-1$$$, если это невозможно.
65aaabc3acb3bac4zbca15czddeneeeemigec13cdefmopqsvxzz
0 1 -1 2 6 0
В первом наборе входных данных строка $$$s$$$ уже отсортирована, поэтому нам не нужны операции.
Во втором наборе входных данных, сделав одну операцию, мы выберем cb и циклически сдвинем её. Теперь строка $$$s$$$ становится равной abc, которая отсортирована.
В третьем наборе входных данных $$$s$$$ не может быть отсортирована.
В четвертом наборе входных данных мы сделаем следующие операции:
Таким образом, нам нужно $$$2$$$ операции.
Название |
---|