Jumbled password

Alice is writing down a secret password as she hears it. The sender reads the password a second time, so she keeps writing to check her copy for mistakes. She gets one letter wrong, and her attention slips for a moment, so she misses the end of the stream. Now she cannot tell where the second reading begins.

You are given a string $S[0 \ldots n-1]$ of lowercase English letters. Find the earliest position where the repeat of the password can start. Formally, find the index $i$ that satisfies all of the following conditions:

• $\frac{n}{2} \le i < n$
• $S[i \ldots n-1]$ and $S[0 \ldots n-i-1]$ differ in exactly one position
• among all indices satisfying the two conditions above, $i$ is the smallest

The first line contains the length of the string, $n$ ($2 \le n \le 500\,000$).

The second line contains the string $S$ of $n$ lowercase English letters.

Print the index $i$ that satisfies the conditions on a single line. If no such index exists, print $-1$ instead.

In the first example the two compared strings are abaa and aaaa.