Palindrome

Task

Little Square found an array $a$ consisting of $N$ positive numbers formed of nonzero digits. He can replace any number from a with another number consisting of as many digits, all nonzero.

After making all the changes he wants, Little Square will form a new number $M$ by writing the elements of the array $a$ in order, without spaces. What is the minimum numbers of elements of the array $a$ which need to be replaced by Little Square for the number $M$ obtained to be a palindrome?

Input data

The first line of the input file palindrome.in will contain an integer $N$, the size of the array $a$. The second line will contain $N$ integers consisting only of nonzero digits representing the array $a$.

Attention! The numbers read from the input file may be too big for the int data type. It is recommended to use the long long data type.

Output data

The output file palindrome.out will contain only one integer, representing the minimum number of elements of the array $a$ that need to be replaced.

Constraints

• $1 \leq N \leq 500 \ 000$
• $1 \leq a_i \lt 10^{18}$, for every $1 \leq i \leq N$
• A number is a palindrome if its first digit is equal to its last one, its second digit is equal is equal to the next to last digit and so on. Thus, numbers $4, 121, 14 \ 541$ are palindromes, while numbers $21, 433, 1 \ 234 \ 312$ are not palindromes.

Example 1

palindrome.in

6
13577 98 348 997 8 31

palindrome.out

2

Explanation

In the first example, Little Square can replace the first number with $13 \ 879$ and the third number with $448$. The number $M$ will become $1 \ 387 \ 998 \ 448 \ 997 \ 831$ which is a palindrome. There is no solution with less than two replacements.

Example 2

palindrome.in

3
455 21 1347742112664

palindrome.out

1

Explanation

In the second example, Little Square can replace the third number with $134 \ 7743 \ 112 \ 554$.