Hide

Problem FFalse Sanctum: Act 2

At the other side of Kivotos, the Trinity General School detected an abnormally high number of monsters in the schoolâ€™s underground system. While many students are trying their best to fend off the monsters, Mika charges in to the center of the anomaly, hoping to find a way to stop the monster raid. Mika finds an obelisk with high concentrations of energy, which is the source of energy of the monsters.

Upon touching the obelisk, a lowercase alphabet letter string $S$ of length $N$ is displayed in a hologram. From the given string $S$, a key must be retrieved to shut down the obelisk. The key of the string $S$ is defined to be the shortest substring such that it is possible to construct the original string $S$ from the substring by concatenating and overlapping operations.

For example, the key to the string abbabbababbab is abbab, as the string can be composed of the key like the following:

S = abbabbababbab key = abbab abbab abbab

As the beloved Sensei of Kivotos students, you decide to help Mika to find the key of string $S$.

Input

The first line of input contains an integer $N$ ($1 \leq N \leq 10^7$), the length of the string $S$.

The second line contains the string $S$ of length $N$ consisting of lowercase alphabet letters.

Output

Output a single integer, the length of the key.

Sample Input 1 Sample Output 1
13
abbabbababbab

5

Hide