You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Frieren最近在研究一本来自神秘西方世界“霍格沃兹学院”遗落在此的魔导书。并且发现了一条神秘的字符带 $S$，这条字符带由小写英文字母组成。传说霍格沃兹的人会使用一种名为“厄里斯魔镜”的魔法，用来显示人内心深处最迫切、最强烈的渴望。他们会将一段咒语写下，并在字符带的另一处写下该咒语的反转形式来封印力量。

为了破解封印，需要找到字符带中存在的一对互不重叠的子串，其中一个子串是另一个子串的反转（例如 "abc" 和 "cba" 互为反转）。

Frieren非常喜欢收集魔法，她需要你的帮助来找出这对镜像子串所能达到的最大长度。

Description

给定一个长度为 $n$ 的字符串 $S$。 求最大的整数 $L$，使得存在四个整数 $l_1, r_1, l_2, r_2$ 满足以下所有条件：

1、$1 \leq l_1 \leq r_1 \leq n$ 且 $1 \leq l_2 \leq r_2 \leq n$；

2、两个子串的长度均为 $L$，即 $r_1 - l_1 + 1 = L$ 且 $r_2 - l_2 + 1 = L$；

3、两个子串所在区间互不重叠，即 $[l_1, r_1] \cap [l_2, r_2] = \emptyset$（等价于 $r_1 < l_2$ 或 $r_2 < l_1$）；

4、子串 $S[l_1 \dots r_1]$ 是子串 $S[l_2 \dots r_2]$ 的反转，即 $S[l_1 \dots r_1]$ 等于 $S[l_2 \dots r_2]$ 的逆序字符串。

Format

Input

第一行包含一个整数 $n$ ($1 \le n \le 1 \times 10^5$)，表示字符串的长度。第二行包含一个字符串 $S$，仅包含小写英文字母。

Output

输出一个整数，表示满足条件的最大长度 $L$。 如果不存在这样的子串对，输出 0。

Samples

7
abcycba

3

5
ababa

2

Limitation

2s, 1024KiB for each test case.