Description

Sometimes the CodesOJ administrators use peculiar methods to hide the registration codes for their monthly contests. Users can only participate after cracking the registration code through certain means. Little Tu selects a string S (composed of N lowercase letters, where 5 ≤ N ≤ 5,000,000), then he arranges S clockwise into a circle. Starting from each letter as the beginning, he sequentially picks letters clockwise to form a string. This generates several strings, which he sorts and takes the first string from the sorted list. The registration code for the OJ contest is then determined by the position of this string's first letter in the original string minus 1.

For example, consider the string "alabala". Following this operation, 7 strings are generated, which when sorted yield:

aalabal

abalaal

alaalab

alabala

balaala

laalaba

labalaa

The first string is "aalabal", whose first 'a' is at position 7 in the original string. Thus, 7 - 1 = 6, so the registration code is 6.

Input Format

First line: An integer: N

Second line onwards: The string S (with a line break every 72 characters)

Output Format

A single line containing the obtained registration code

```input1 7 anabana ``` ```output1 6 ``` ## Hint

【Data Range】

30% of data: n ≤ 10,000

70% of data: n ≤ 100,000

100% of data: n ≤ 5,000,000

Source

Adapted original problem from CodesOJ