P1709 [USACO5.5] Hidden Password

Sometimes programmers have quirky ways to hide their passwords. Binny chooses a string $S$ (consisting of $N$ lowercase letters, $5 \le N \le 5 \times {10}^6$). He arranges $S$ on a circle clockwise, then for each position he takes that character as the starting letter and reads clockwise to form a string. This produces $N$ strings. He sorts these strings and takes the first one. The password is defined as the position of the first letter of this string in the original string, minus $1$. For example, for the string `alabala`, the operation yields $7$ strings. After sorting, they are: `aalabal` `abalaal` `alaalab` `alabala` `balaala` `laalaba` `labalaa` The first string is `aalabal`. The first character `a` corresponds to position $7$ in the original string, so $7 - 1 = 6$, and $6$ is the password.

The first line: an integer $N$. Starting from the second line: the string $S$ (a newline is inserted after every $72$ characters).

One line containing the resulting password.

The problem satisfies: $30 \%$ 的数据 $n \le {10}^4$。 $70 \%$ 的数据 $n \le {10}^5$。 $100 \%$ 的数据 $1 \le n \le 5 \times {10}^6$。 Time limit: 1 s. Problem translation from NOCOW. USACO Training Section 5.5. // 20170523 added four testdata sets. Translated by ChatGPT 5