题目描述

阿兔是马拉车算法的高手，同时也对回文串情有独钟。然而，现实中并非所有字符串都能自然地构成回文。

对于一个字符串 $t$，如果阿兔能够通过修改其中一个字符，使其变成回文串，那么他就称这个字符串为“瑕疵回文串”。

现在，阿兔给你一个长度为 $n$ 的字符串 $s$，并希望你能帮助他找出在这个字符串的所有子串中，最长的“瑕疵回文串”的长度是多少？

回文串是一个从左到右和从右到左都相同的字符串。例如 $“abacaba”$ 、$“zimemiz”$ 都是回文串，而 $“atuer”$ 不是。

子串是字符串中任意连续的一段字符，例如 $“zime”$ 、$“hanhan”$ 都是 $“zimehanhan”$ 的子串，而 $“zhanhan”$ 不是。

输入格式

第一行是一个正整数 $n \ (1\leq n \leq 2*10^{5})$，表示字符串。 第二行是一个长度为 $n$ 的字符串，仅由小写字母组成。

输出格式

输出一行包含一个整数，表示子串中最长的“瑕疵回文串”的长度。

5
atuer

3

解释 #1

$“atu”$ 是子串中最长的“瑕疵回文串”。

13
genshinimpact

5

解释 #2

$“hinim”$ 是子串中最长的“瑕疵回文串”。

3
ioi

3

解释 #3

$“ioi”$ 是子串中最长的“瑕疵回文串”。