15211번 - Jumbled password 다국어

문제

Alice is receiving a very secret password. As she's receiving it, she's writing it down. Oh, look! They are repeating the password once again! Let's write it down so that we can find any possible mistakes!

And so she's writing it down, when she suddenly realizes that she's made a mistake in one of the letters! Oh no, she's also lost attention for a short while and she missed the end of the stream! And to make matters worse, she can't distinguish the end of the first repetition of the password! Who's gonna help her recover the password?

You are given a string $S[0 \ldots (n-1)]$ of lower case english letters. Find the first position $i$ in the string that could mark the start of the password repeat. Formally, find index $i$ satisfying the following conditions:

• $\frac{n}{2} \leq i < n$
• There is \textbf{exactly} one-character difference between the substrings $S[i\ldots (n-1)]$ and $S[0\ldots (n - i - 1)]$
• Of all the indices satisfying previous two conditions, $i$ is the smallest one.

입력

The first line of the input contains $n$ (2ドル \leq n \leq 500,000円$), the number of characters in the string.

The second line contains string $S$ (consisting of lower case english letters).

출력

Output a single line with index $i$ satisfying the conditions. If no such index exists, output $-1$ instead.

제한

힌트

The corresponding strings are abaa and aaaa.