Nông dân John khao khát giành được giải thưởng bức ảnh con bò xuất sắc nhất tại hội chợ, đang cố gắng chụp bức ảnh hoàn hảo về \(N\) con bò của mình \((2 \leq N \leq 2*10^5, N\) chẵn\()\)
Nông dân John sở hữu \(2\) giống bò tiềm năng: Guernseys và Holsteins. Để làm cho bức ảnh của mình tốt nhất có thể, anh ấy muốn xếp những con bò của mình sao cho càng nhiều con bò Guernsey ở các vị trí chẵn trong hàng càng tốt (vị trí đầu tiên trong hàng là vị trí lẻ, tiếp theo là vị trí chẵn, ...). Do không giỏi giao tiếp với những con bò của mình, cách duy nhất để anh ta có thể đạt được mục tiêu là đảo ngược thứ tự của một dãy \(j\) con bò đầu tiên với \(j\) chẵn.
Hãy đếm số lần đảo ngược cần ít nhất để Nông dân John đạt được mục tiêu của mình.
Input
- Dòng đầu tiên chứa số \(N\).
- Dòng thứ hai chứa một xâu độ dài \(N\), theo thứ tự ban đầu của các con bò từ trái sang phải. Chữ
H
tượng trưng cho bò Holstein, trong khi chữG
tượng trưng cho bò Guernsey.
Output
In ra số lần đảo ngược tối thiểu cần thiết.
Scoring
- Subtask \(1\): \(N \leq 1000\).
- Subtask \(2\): Không có điều kiện gì thêm.
Example
Test 1
Input
14
GGGHGHHGHHHGHG
Output
1
Note
- Trong ví dụ này, chỉ cần đảo ngược thứ tự của sáu con bò đầu tiên là đủ:
GGGHGHHHHHHGHG
->HGHGGGHHHHHHG
. - Trước khi đảo ngược, có bốn con bò Guernseys ở vị trí chẵn. Sau khi đảo ngược, có sáu con bò Guernseys ở vị trí chẵn. Không thể có nhiều hơn sáu con bò Guernsey ở các vị trí chẵn.
Bình luận