Description

Let the reversal of a string $w$ be denoted by $w^{\mathsf R}$. For example, $\tt (abcd)^{\mathsf R}=dcba$, $\tt (abba)^{\mathsf R}=abba$.

For a string $x$, if $x$ satisfies $x^{\mathsf R}=x$, it is called a palindrome. For example, $\tt abba$ is a palindrome, while $\tt abed$ is not.

If $x$ can be written in the form $ww^{\mathsf R} ww^{\mathsf R}$, it is called a "double palindrome". In other words, for $x$ to be a double palindrome, the length of $x$ must be a multiple of $4$, and $x$, its first half, and its second half must all be palindromes. For example, $\tt abbaabba$ is a double palindrome, while $\tt abaaba$ is not, because its length is not a multiple of $4$.

• A substring of $x$ is a string formed by a consecutive segment of characters in $x$. For example, $\tt be$ is a substring of $\tt abed$, while $\tt ac$ is not.
• A palindromic substring of $x$ is a substring of $x$ that is a palindrome.
• A double palindromic substring of $x$ is a substring of $x$ that is a double palindrome.

Your task is to compute the length of the longest double palindromic substring of the given string.

Input Format

The input consists of two lines.

• The first line contains an integer $N$, the length of the string.
• The second line contains a string of lowercase English letters, which is the content of the string.

Output Format

Output a single line: the length of the longest double palindromic substring of the input string. If no double palindromic substring exists, output $0$.

16
ggabaabaabaaball

12

Hint

Constraints

For all testdata, $1 \le N \le 500000$.

Translated by ChatGPT 5