뒤섞인 비밀번호

앨리스는 비밀번호를 들으면서 받아 적고 있다. 상대가 비밀번호를 한 번 더 불러 주기에, 잘못 적은 곳이 없는지 확인하려고 계속 받아 적는다. 그런데 글자 하나를 잘못 적었고, 잠시 집중이 흐트러진 사이에 뒷부분을 놓쳤다. 그래서 두 번째 반복이 어디서 시작하는지 알 수 없다.

영어 소문자로 이루어진 문자열 $S[0 \ldots n-1]$이 주어진다. 비밀번호의 반복이 시작될 수 있는 가장 앞 위치를 찾아라. 정확히는 다음 조건을 모두 만족하는 인덱스 $i$를 구한다.

• $\frac{n}{2} \le i < n$
• $S[i \ldots n-1]$과 $S[0 \ldots n-i-1]$이 정확히 한 자리에서만 다르다
• 앞의 두 조건을 만족하는 인덱스 중에서 $i$가 가장 작다

첫째 줄에 문자열의 길이 $n$이 주어진다 ($2 \le n \le 500\,000$).

둘째 줄에 영어 소문자로 이루어진 길이 $n$의 문자열 $S$가 주어진다.

조건을 만족하는 인덱스 $i$를 한 줄에 출력한다. 그런 인덱스가 없으면 $-1$을 출력한다.

첫 번째 예제에서 비교하는 두 문자열은 abaa와 aaaa다.