PALSEQ

A string is called a palindrome when it reads exactly the same both from left to right and from right to left. For example, the strings "MADAMIMADAM" and "ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ" are palindromes.

You are given a string and are asked to find the minimum number of its characters that need to be deleted so that the remaining string is a palindrome.

Input

The program reads the data from the text file "palseq.in". The first line contains an integer ~N~, which is the length of the string. The second line contains the ~N~ characters that make up the string.

Output

The result should be printed to the text file "palseq.out". Only one line should be printed, containing a natural number: the minimum possible number of characters from the original string that, if deleted, the remaining string is a palindrome.

Constraints

• ~1 \le N \le 20.000~.
  
• Time Limit: 3 sec.
  
• Maximum Available Memory: 16 MB.

Example of Input - Output

STDIN (palseq.in)

20
bbccaddabaddacaaacdb

STDOUT (palseq.out)

5