410121: GYM103960 A Finding Maximal Non-Trivial Monotones

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Finding Maximal Non-Trivial Monotonestime limit per test0.25 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

In this problem we will be dealing with character sequences, often called strings. A sequence is non-trivial if it contains at least two elements.

Given a sequence $$$s$$$, we say that a chunk $$$s_i, \ldots, s_j$$$ is monotone if all its characters are equal, and we say that it is maximal if this chunk cannot be extended to left or right without losing the monotonicity.

Given a sequence composed only of characters "a" and "b", determine how many characters "a" occur in non-trivial maximal monotone chunks.

Input

The input consists of two lines. The first line contains a single integer $$$N$$$, where $$$1 \leq N \leq 10^5$$$. The second line contains a string with exactly $$$N$$$ characters, composed only of the characters "a" and "b".

Output

Print a single line containing an integer representing the total number of times the character "a" occurs in non-trivial maximal monotone chunks.

ExamplesInput
7
abababa
Output
0
Input
7
bababab
Output
0
Input
10
aababaaabb
Output
5
Input
10
bbaababaaa
Output
5

加入题单

上一题 下一题 算法标签: