Nguồn đề: Free contest 126

Đề bài: https://drive.google.com/file/d/1gpMCqTKMpHQCAV7_OmOSVQnWuxSTzobn/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1rCpSEQ8Y8eyXVfkHjsgT4yFWkuK1DSpf/view?usp=sharing

Bài giải: https://drive.google.com/file/d/1PoXm1kEXub1YQ9gIqCGdzuqhxo00S-fz/view?usp=sharing

Bạn được cho một xâu gồm N kí tự liền kề nhau. Mỗi kí tự có thể là kí tự 'a', 'b' hoặc '?'. Ta có thể thay thế những kí tự '?' trong xâu ban đầu thành kí tự 'a' hoặc kí tự 'b'.

Giả sử chúng ta đã thay thế hết các kí tự '?', thì với mỗi cặp hai kí tự liền kề nhau trong xâu ban đầu, chúng ta định nghĩa giá trị của cặp đó như sau:

• 'aa' = 0
• 'ab' = 1
• 'bb' = 0
• 'ba' = -1

Tổng giá trị của một xâu là tổng giá trị của n - 1 cặp hai kí tự liền kề.

Bài toán đặt ra cho bạn là trong tất cả các cách thay thế những kí tự '?' trong xâu ban đầu, bạn hãy in ra tổng giá trị lớn nhất có thể.

Input

Dòng 1: n độ dài của xâu ~(1 ≤ n ≤ 10^6).~

Dòng 2: Một xâu gồm n kí tự.

Kết quả

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể trong tất cả các cách thay thế.

Sample Input 1

5
aabbb

Sample Output 1

1

Sample Input 2

6
a?a?bb

Sample Output 2

1

Sample Input 3

5
b????

Sample Output 3

0

Giải thích

Ở test ví dụ 1, ta có từng cặp xâu liên tiếp là 'aa', 'ab', 'bb', 'bb', tổng giá trị của xâu là 0 + 1 + 0 + 0 = 1

Ở test ví dụ 2, ta có thể thay thế các kí tự '?' thành xâu ababbb. Những cặp xâu liên tiếp là 'ab', 'ba', 'ab', 'bb', 'bb', tổng giá trị của xâu là 1 + (-1) + 1 + 0 + 0 = 1

Ở test ví dụ 3, ta có thể thay thế các kí tự '?' thành xâu bbbbb, tổng giá trị của xâu là 0.