Alice 正在接收一个非常机密的密码。在接收过程中，她将其记录了下来。噢，看！他们把密码又重复了一遍！让我们把它写下来，以便找出可能存在的错误！
就在她记录的时候，她突然意识到自己在其中一个字母上犯了错误！糟糕的是，她还走神了一会儿，错过了流的结尾！更糟糕的是，她无法区分密码第一次重复的结束位置！谁能帮她找回密码呢？
给定一个由小写英文字母组成的字符串 $S[0 \dots (n-1)]$。请找出字符串中可能标记密码重复开始的第一个位置 $i$。形式化地，请找到满足以下条件的索引 $i$：
- $\frac{n}{2} \le i < n$
- 子串 $S[i \dots (n-1)]$ 与 $S[0 \dots (n-i-1)]$ 之间恰好有一个字符的差异。
- 在所有满足上述两个条件的索引中，$i$ 是最小的一个。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示字符串的长度。第二行包含字符串 $S$（由小写英文字母组成）。
输出格式
输出一行，包含满足条件的索引 $i$。如果不存在这样的索引，则输出 $-1$。
子任务
| 子任务 | 分值 | 最大 $n$ |
|---|---|---|
| 1 | 25 | 20 |
| 2 | 25 | 5000 |
| 3 | 50 | 500000 |
样例
输入格式 1
8 abaaaaaa
输出格式 1
4
说明
对应的字符串是 abaa 和 aaaa。
输入格式 2
9 abcdefghi
输出格式 2
8
输入格式 3
5 aaaaa
输出格式 3
-1