Problem F
False 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 |
