题目描述

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

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

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

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

输入格式

第一行一个整数 $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$。