[Poi2012]Prefixuffix

对于两个字符串 $S_1$ 和 $S_2$，如果将 $S_1$ 的一个后缀移动到开头后可以得到 $S_2$，则称 $S_1$ 和 $S_2$ 循环相同。例如，字符串 ababba 和 abbaab 循环相同。

给定一个长度为 $n$ 的字符串 $S$，求满足以下条件的最大整数 $L$：

1. $L\le n/2$；
2. $S$ 的长度为 $L$ 的前缀与长度为 $L$ 的后缀循环相同。

输入格式

第一行包含一个正整数 $n$，满足 $n\le 10^6$。

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

输出格式

输出一个整数，表示满足条件的最大 $L$。

样例输入

15
ababbabababbaab

样例输出

6

数据范围

• $n\le 10^6$。

来源与许可

本题为 POI 2012 试题「Prefixuffix」，题面与测试数据整理自 BZOJ 2803。

样例 1

输入

15
ababbabababbaab

输出

6