Trong quá trình khám phá ngôi nhà, Long bất ngờ vào được phòng riêng của nhà toán học. Ở đây, cậu tìm được một bức thư mà nhà toán học gửi cho người yêu của mình. Tuy nhiên, bức thư được mã hoá nên cậu cần tìm cách để giải mã nó:

Bức thư là 1 xâu gồm N kí tự. Mỗi kí tự có thể là kí tự ‘a’, ‘b’ hoặc ‘?’. Để giải mã, 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 là trong tất cả các cách thay thế những kí tự ‘?’ trong xâu ban đầu, hãy in ra tổng giá trị lớn nhất có thể, từ đó có thể giải được bức thư. Các bạn hãy giúp Long nhé!

Dữ liệu: Vào từ file LONGXAU.INP gồm:

+ Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 10⁶).

+ 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 ‘?’.

Kết quả: Ghi ra file LONGXAU.OUT 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ế.

Ví dụ:

Ràng buộc:

+ 50% số điểm có N ≤ 20;

+ 50% số điểm còn lại, không có ràng buộc gì thêm.