Chụp Ảnh

Farmer John muốn sắp xếp $N$ con bò ($2\le N\le 2\times {10}^5$, $N$ chẵn) đứng thành hàng sao cho số bò Guernsey chiếm vị trí chẵn là nhiều nhất có thể. Mỗi con bò hoặc là Guernsey (G) hoặc Holstein (H).

Phép toán duy nhất mà Farmer John có thể thực hiện là đảo ngược một tiền tố có độ dài chẵn. Hãy tìm số lần đảo ngược tối thiểu cần thực hiện để đạt được cách sắp xếp tối ưu.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: Xâu ký tự độ dài $N$ gồm các ký tự 'G' và 'H'

Dữ liệu ra

Một số nguyên duy nhất — số lần đảo ngược tiền tố tối thiểu cần thực hiện.

Ràng buộc

• $2\le N\le 2\times {10}^5$, $N$ chẵn
• Test 2-6: $N\le 1000$
• Test 7-11: Không có ràng buộc thêm

Ví dụ