|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
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