Вам даны две строки \(s\) и \(t\) равной длины \(n\). За одну операцию вы можете поменять местами любые два соседних символа в строке \(s\).
Вам нужно сказать, какое наименьшее количество операций вам потребуется, чтобы строка \(s\) стала лексикографически меньше строки \(t\).
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого тестового случая в отдельной строке выведите наименьшее количество операций, которое вам потребуется, чтобы строка \(s\) стала лексикографически меньше строки \(t\), или \(-1\), если это невозможно сделать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
a
a
3
rll
rrr
3
caa
aca
5
ababa
aabba
|
-1
0
2
2
|