Palindrome

A palindrome is a string that reads the same both forwards and backwards. For example, the string «ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ» is a palindrome.

Problem:

Develop a program in one of the IOI languages which: after reading a string, will calculate the length of the smallest palindrome that can be constructed with this string as a prefix.

Input Files:

The input files named minpali.in are text files with the following structure: The first line contains an integer ~N\;(1 \le N \le 10.000.000)~, the number of characters in the string. The second line contains successively the ~N~ characters of the string.

Output Files:

The output files named minpali.in are text files with the following structure: they have one line with exactly one number, the length in characters of the smallest palindrome that can be constructed with the given string as a prefix.

Examples of Input-Output Files:

1st

STDIN (minpali.in)

6
abcdef

STDOUT (minpali.out)

11

2nd

STDIN (minpali.in)

10
abccbbabbc

STDOUT (minpali.out)

13

Explanation of the Examples:

The smallest possible palindromes are "abcdefedcba" and "abccbbabbccba", with lengths ~11~ and ~13~, respectively.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.