F - Antipalindromes

Time limit: 1 s
Memory limit: 2048 MiB
Languages: C, C++, Java, Python, ... (details)

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.

Input

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.

Output

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

Sample test(s)

Input
4 0101
Output
4
Input
4 1001
Output
2