Dance School

Interview

Time limit2sMemory limit512 MB

Summary

Given a string of 'a' and 'b' of length up to 10^6, count the substrings in which the number of a's equals the number of b's.

Level: Medium5 of 10
Topics: Prefix sum, Hash map, Combinatorics, String
Solved: No attempts yet

Statement

n students, boys and girls, enrolled at Professor Padegras's ballroom dance school. The professor lined them up in a single row and wants to pick, for the first lesson, a group of students standing consecutively whose number of boys equals its number of girls. How many ways can the professor make this choice?

Input

The first line contains n (1 ≤ n ≤ 10^6). The second line contains a string of n characters describing the row, each character being a or b, where a denotes a girl and b denotes a boy.

Output

Print a single number: the number of ways to choose a valid group.

Examples2

Example 1
Input
```
3
bab
```
Expected output
```
2
```
Example 2
Input
```
8
abbababa
```
Expected output
```
13
```