J. Наибольший сдвиг

Среди всех циклических сдвигов строки найдите лексикографически наибольший и выведите наименьшую позицию, с которой он начинается.

Алгоритм тот же, что в классе, но знак сравнения переворачивается: проигравшим считается тот кандидат, у которого символ меньше.

Досборка наименьшей позиции нужна ровно так же: у периодичной строки наибольший сдвиг тоже встречается несколько раз.

Если хочется проверить себя другим способом: наибольший сдвиг строки $s$ — это наименьший сдвиг строки, в которой каждая буква заменена на противоположную по алфавиту. Способ рабочий, но лишний; менять знак проще.

Одна строка длины $n$ ($1 \le n \le 10^6$) из строчных латинских букв.

Одно число — наименьшая позиция (нумерация с нуля), с которой начинается лексикографически наибольший циклический сдвиг.