在本题中，我们考虑由小写英文字母组成的字符串。给定字符串的起始片段称为前缀，末尾（终止）片段称为后缀。特别地，空字符串既是任何字符串的前缀，也是其后缀。如果一个字符串可以通过将另一个字符串末尾的某个后缀移动到开头而得到，则称这两个字符串循环等价。例如，字符串 ababba 和 abbaab 是循环等价的，而 ababba 和 ababab 则不是。特别地，每个字符串都与自身循环等价。

给定一个长度为 $n$ 的字符串 $t$。我们需要找到其长度相等的前缀 $p$ 和后缀 $s$，使得：

• $p$ 和 $s$ 循环等价，
• $p$ 和 $s$ 的公共长度不超过 $n/2$（即前缀 $p$ 和后缀 $s$ 在 $t$ 中不重叠），以及
• $p$ 和 $s$ 的公共长度最大化。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示字符串 $t$ 的长度。输入的第二行包含字符串 $t$ 本身，由 $n$ 个小写英文字母组成。

输出格式

程序应在标准输出的第一行（也是唯一一行）打印一个整数，即我们所寻找的前缀 $p$ 和后缀 $s$ 的最大公共长度。

样例

输入 1

15
ababbabababbaab

输出 1

6