Question
The Vowels Melody
You are given a string s of length n, consisting of lowercase English letters.
We define a valid subarray (substring) as one where the parity (even/odd) of occurrences of all vowels (a, e, i, o, u) is the same.
-
That means either all five vowels occur an even number of times, or all five occur an odd number of times in that substring.
Your task is to determine the total number of valid substrings of s.
Input
The first line contains an integer KaTeX can only parse string typed expression — the length of the string.
The second line contains the string s, consisting only of lowercase English letters.
The second line contains the string s, consisting only of lowercase English letters.
Output
Print a single integer — the number of valid substrings.
Example
Input
5
aeiou
Output
1
Explanation
The whole string "aeiou" is the only valid substring because all vowels appear exactly once (all odd).
Input
6
abcabc
Output
9
Explanation
"b" (Index 2 to 2)
"c" (Index 3 to 3)
"bc" (Index 2 to 3)
"b" (Index 5 to 5)
"c" (Index 6 to 6)
"bc" (Index 5 to 6)
"abca" (Index 1 to 4)
"abcab" (Index 1 to 5)
"abcabc" (Index 1 to 6)
5
aeiou
Output
1
Explanation
The whole string "aeiou" is the only valid substring because all vowels appear exactly once (all odd).
Input
6
abcabc
Output
9
Explanation
"b" (Index 2 to 2)
"c" (Index 3 to 3)
"bc" (Index 2 to 3)
"b" (Index 5 to 5)
"c" (Index 6 to 6)
"bc" (Index 5 to 6)
"abca" (Index 1 to 4)
"abcab" (Index 1 to 5)
"abcabc" (Index 1 to 6)