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ề 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 tất cả ~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 đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^6)~.
• Dòng tiếp theo chứa một xâu gồm ~N~ kí tự, mỗi kí tự có thể là kí tự a, b hoặc ?.

Output

• 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ế.

Samples

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

Clarification

• Ở 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ế thành xâu bbbbb, tổng giá trị của xâu là ~0~.

Scoring

• Subtask ~1~ (~50\%~ số test): ~N \le 20~
• Subtask ~2~ (~50\%~ số test): Không có ràng buộc gì thêm