A binary string is considered antipalindrome if it is not empty and it is fulfilled for each $i$ that $s_i \neq s_{n - i + 1}$. For example, 01, 0011, 101010 and 011001 are antipalindromes, but 0, 1110, 11, are not.

Given a binary string, determine how many substrings are antipalindromes. If the amount of antipalindromes substrings is greater than $10^5$, print $10^5$ instead.

A line with a number $n (1 \leq n \leq 10^5)$, the size of the string. In second line, a binary string of $n$ characters.

Print the amount of substrings that are antipalindromes, in case being greater than $10^5$, print $100 000$.

Input

4
0101

Output

4

Input

4
1001

Output

2