题目描述

给定一个长度为 $n$ 的字符串 $s$，找到满足如下条件的最大整数 $m$：

• $0 \le m \lt n$；
• 字符串 $s$ 的长度为 $m$ 的前缀和长度为 $m$ 的后缀相同。

输入格式

第一行，一个整数 $n(1 \le n \le 10^6)$。

第二行，一个长度为 $n$ 的字符串 $s$。$s$ 仅由小写英文字母组成。

输出格式

输出满足条件的最大整数 $m$。

样例

7
abacaba

3

8
abbabbab

5

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 100$；
• 对于 $60\%$ 的数据，$n \le 10000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，字符串 $s$ 仅由小写英文字母组成。