[SHOI2011] 双倍回文

题目描述

记字符串 $w$ 的倒置为 $w^{\mathsf R}$。例如$\tt (abcd)^{\mathsf R}=dcba$,$\tt (abba)^{\mathsf R}=abba$。 对字符串 $x$,如果 $x$ 满足 $x^{\mathsf R}=x$,则称之为回文。例如 $\tt abba$ 是一个回文,而 $\tt abed$ 不是。 如果 $x$ 能够写成 $ww^{\mathsf R} ww^{\mathsf R}$ 形式,则称它是一个“双倍回文”。换句话说,若要 $x$ 是双倍回文,它的长度必须是 $4$ 的倍数,而且 $x$,$x$ 的前半部分,$x$ 的后半部分都要是回文。例如 $\tt abbaabba$ 是一个双倍回文,而 $\tt abaaba$ 不是,因为它的长度不是 $4$ 的倍数。 - $x$ 的子串是指在 $x$ 中连续的一段字符所组成的字符串。例如 $\tt be$ 是 $\tt abed$ 的子串,而 $\tt ac$ 不是。 - $x$ 的回文子串,就是指满足回文性质的 $x$ 的子串。 - $x$ 的双倍回文子串,就是指满足双倍回文性质的 $x$ 的子串。 你的任务是,对于给定的字符串,计算它的最长双倍回文子串的长度。

输入输出格式

输入格式


输入分为两行。 第一行为一个整数,表示字符串的长度。 第二行有个连续的小写的英文字符,表示字符串的内容。

输出格式


输出文件只有一行即输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出 $0$。

输入输出样例

输入样例 #1

16
ggabaabaabaaball

输出样例 #1

12

说明

### 数据范围及约定 对于全部数据,$1\le N \le 500000$。