(gmatthu.*)

Trong hội trại năm nay, Tí được lớp giao nhiệm vụ tham gia trò chơi giải mật thư tìm kho báu. Mật thư có \(n\) kí tự chỉ gồm hai loại kí tự là ‘A’ và ‘B’. Trong mật thư nếu số lần chuỗi con “AA” xuất hiện nhiều hơn số lần xuất hiện của chuỗi con “BB” thì đáp án của mật thư là số lần xuất hiện chuỗi con “AA” và ngược lại.

Tí vô tình làm ướt mật thư nên một số kí tự có thể bị nhòe mực, lúc này kí tự nào bị nhòe thì kí tự đó sẽ chuyển thành kí tự ‘*’.

Yêu cầu: Hãy giúp Tí tìm ra một số lớn nhất có thể là đáp án của mật thư nếu nó không bị ướt.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(n\) là độ dài của mật thư \((1 \leq n \leq 10^{6})\).

+ Dòng thứ hai chứa \(n\) kí tự ‘A’, ‘B’ hoặc ‘*’ được ghi liên tiếp không chứa dấu cách.

Kết quả: Ghi một số nguyên duy nhất là đáp án của bài toán.

Ví dụ:

Giới hạn:

+ 50% test tương ứng 50% số điểm với mật thư chỉ gồm hai kí tự ‘A’ và ‘B’.

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