P8266 [USACO22OPEN] Photoshoot B

Farmer John, who is eager to win the prize for best cow photographer at the county fair, is trying to take a perfect photo of his $N$ cows ($2 \leq N \leq 2\cdot 10^5$, and $N$ is even). Farmer John has two breeds of cows: Guernsey and Holstein. To make his photo as artistic as possible, he wants to line up his cows in a row so that as many Guernsey cows as possible are in the even positions of the line (the first position is odd, the next is even, and so on). Because he cannot communicate well with his cows, the only way he can achieve this is by reversing an even-length prefix of the line (a prefix means, for some position $j$, all cows from the first cow to the $j$-th cow). Compute the minimum number of reversals Farmer John needs to achieve his goal.

The first line contains the value of $N$. The second line contains a string of length $N$, giving the initial arrangement of the cows from left to right. Each 'H' represents a Holstein cow, and each 'G' represents a Guernsey cow.

Output one line containing the minimum number of reversals needed to achieve the goal.

[Sample Explanation] In this example, it is enough to reverse the prefix consisting of the first six cows. ``` GGGHGHHGHHHGHG （before reversal） -> HGHGGGHGHHHGHG （after reversal） ``` Before the reversal, four Guernsey cows are in even positions. After the reversal, six Guernsey cows are in even positions. It is impossible to make more than six Guernsey cows be in even positions. [Test Point Properties] - Test points 2-6 satisfy $N \le 1000$. - Test points 7-11 have no additional constraints. Translated by ChatGPT 5