407774: GYM102892 3 Infectious Letters

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

Description

3. Infectious Letterstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have a string of length $$$n$$$. Unfortunately, some of its letters are infectious. More specifically, any "a" characters in the string have the potential to spread to any adjacent characters. At any point in time, an "a" character in the string can "infect" any of its adjacent characters, and make them an "a" character as well.

However, "b" characters are immune to the "a" characters' infection, and thus can't be changed into "a" characters.

For example, if we have the string "cabaccabdd", the second character of the string could infect the first character, turning it into another "a", but it couldn't infect the third character of the string, since it's a "b".

Your task is to determine the maximum number of $$$a$$$ characters that could exist in the string after an unlimited amount of infections.

For example, in the string "cabaccabdd" could become "aabaaaabdd" in an unlimited number of infections, which has 6 "a" characters.

Input

The first line of input contains a single positive integer $$$n$$$ $$$(1 <= n <= 200000)$$$: the length of the string.

The next line of input contains the string.

Output

Output the maximum number of $$$a$$$ characters that could exist in the string after an unlimited amount of infections.

Scoring

Full problem: 10 points

ExamplesInput
15
bbbacxdbxyabxab
Output
9
Input
5
bbbbb
Output
0
Input
5
aabcc
Output
2

加入题单

上一题 下一题 算法标签: