J. Наименьший сдвиг

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

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

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