题目描述

对于两个串 $S_1, S_2$，如果能够将 $S_1$ 的一个后缀移动到开头后变成 $S_2$，就称 $S_1$ 和 $S_2$ 循环相同。例如串 $\tt ababba$ 和串 $\tt abbaab$ 是循环相同的。

给出一个长度为 $n$ 的串 $S$，求满足下面条件的最大的 $L(L\leq \frac n 2)$：$S$ 的 $L$ 前缀和 $S$ 的 $L$ 后缀是循环相同的。

输入格式

第一行包含一个正整数 $n$，表示字符串 $t$ 的长度。

第二行包含一个由 $n$ 个小写字母构成的字符串 $t$。

输出格式

一行一个整数，表示最大的 $L$。

15
ababbabababbaab

6

提示

数据范围：

• 对于 $30\%$ 的数据，保证 $n\le 500$；
• 对于 $50\%$ 的数据，保证 $n\le 5000$；
• 对于 $100\%$ 数据，保证 $1\le n\le 10^6$。