[AdditionalFile2704.zip](file://AdditionalFile2704.zip?type=additional_file)

#2704. 「POI2012 R3」前后缀 Prefixuffix

标签: 传统 | 时间限制: 1000 ms | 内存限制: 64 MiB |

题目描述

译自 POI 2012 Stage 3. Day 2「Prefixuffix」

如果能把字符串的一个后缀移动到开头得到另一个字符串，则这两个字符串称为「循环等价」。

给定由 $n$ 个小写字母组成的字符串 $t$，求它的一个长度相同的前缀和后缀，满足：

• 前缀和后缀循环等价；
• 前缀和后缀的长度不超过 $\frac n2$（即在 $t$ 内不相交）；
• 满足上述条件的情况下，使前缀和后缀的长度最大。

输入格式

第一行一个整数 $n (1 \le n \le 1\ 000\ 000)$，表示字符串 $t$ 的长度。

接下来一行为字符串 $t$，由 $n$ 个小写字母组成。

输出格式

输出一个整数，表示前缀和后缀的长度。

样例

输入

15
ababbabababbaab

输出

6

数据范围与提示

对于 $30\%$ 的数据，保证 $n \le 500$；

对于 $50\%$ 的数据，保证 $n \le 5000$；

对于所有数据，保证 $n \le 1\ 000\ 000$。