시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 1024 MB222100.000%

문제

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.

예제 입력 1

8
abaaaaaa

예제 출력 1

4

예제 입력 2

9
abcdefghi

예제 출력 2

8

예제 입력 3

5
aaaaa

예제 출력 3

-1

힌트

The corresponding strings are abaa and aaaa.