说明

一些前置定义：

• $\text{Rev}(S):$ $S_{|S|},S_{|S|-1},\dots,S_1$ 顺次相连形成的字符串。即将 $S$ 翻转。

• $\text{lcp}(i,j):$ 第 $i$ 个位置开始的后缀与第 $j$ 个位置开始的后缀的最长公共前缀对应的字符串。

• $\text{lcs}(i,j):$ 第 $i$ 个位置结束的前缀与第 $j$ 个位置结束的前缀的最长公共后缀对应的字符串。

• $\text{LCP}(S,T):$ $S$ 和 $T$ 的最长公共前缀。

---

给出长度为 $n$ 的字符串 $S$，求：

$$\max\limits_{1 \le i < j \le n}\{\text{LCP}(\text{Rev}(\text{lcs}(i,j)),\text{lcp}(i,j))\}$$

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $S$。

输出格式

输出为一个数，即答案。

9
abbbabbba

3

提示

样例一解释

$\text{lcp}(3,7):$ bba。

$\text{lcs}(3,7):$ abb。

$\text{LCP}(\text{Rev}(\texttt{\color{blue}abb}),\texttt{\color{blue}bba}):$ bba。

可以证明，没有比 $i=3,j=7$ 更优的方案。

数据范围与约束

对于 $30\%$ 的数据，$1 \le n \le 2\times 10^3$。

对于 $60\%$ 的数据，$1 \le n \le 10^5$。

对于另外 $10\%$ 的数据，$\forall 1 \le i \le n-2,S_{i}\not=S_{i+2}$。

对于 $100\%$ 的数据 $1 \le n \le 10^6$，输入均为整数和小写字母。