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ề.

Yêu cầu: 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

• Tổng giá trị lớn nhất có thể đạt được.

Sample

Input #1

5
aabbb

Output #1

1

Input #2

6
a?a?bb

Output #2

1

Hint

• Giải thích #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~.
• Giải thích #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~.