Tracy has a string of ~N~ lowercase alphabetical characters. She would like to choose a point on her string between two characters to be the center of a special palindrome. She can remove characters from the beginning or end of the string to make her special palindrome.

A palindrome is defined as special if it has ~2~ of the same letter in the center, and each letter from the center is repeated ~i + 2~ times, where ~i~ is the distance from the center. That is, the center of the palindrome should have ~2~ of the same letter, then ~3~, then ~4~, and so on. In addition, each repeated section of the same letter should be of a different letter than those adjacent to it.

Can you output the length of the longest special palindrome Tracy can make?

Input Specification

The first line will contain one integer ~N (1 \leq N \leq 6 \times 10^3)~, the length of Tracy's string.

The next line will contain ~N~ lowercase alphabetical characters, Tracy's string.

Output Specification

Output a single integer, the length of the longest special palindrome Tracy can make. If Tracy cannot make a special palindrome, output -1.

Sample Input 1

36
aloifinoddddbbbzzbbbddddllakwifoidgl

Sample Output 1

16

Explanation for Sample 1

The longest special palindrome Tracy can make is ddddbbbzzbbbdddd.

Sample Input 2

30
slkdgjsngasdioawiawjklgawleawf

Sample Output 2

-1