Palindromic Deletion

Albert's many years of competitive programming have addled his brain to the point where he loves palindromes and has signed up to a palindromic challenge (I know, its a sad point to get to). Every week, he gets a string of uppercase, alphabetic characters in the mail and has to delete a substring and send the modified string back as a palindrome. Because he is a "serious" programmer, he'd like to send the longest palindrome that he can.

Input Specification

The first line will contain the number \(N\), the length of the string to follow. The following line will contain a string of \(N\) uppercase letters.

Output Specification

Print the length of the longest palindrome Albert can make.

Bounds

This problem has three sub-problems of varying difficulty.

• 30 points: \(0 \leq N \leq 50\)
• 70 points: \(50 < N \leq 3000\)
• 100 points: \(3000 < N \leq 10^5\)

Example Input

3
ABA

Example Output

3

Example Input

3
AAB

Example Output

2