Optimal Prefix Reversal for Cow Photography

Farmer John has N cows (2 ≤ N ≤ 2×10^5, and N is even), each of which is of one of two breeds: Guernsey (denoted by 'G') and Holstein (denoted by 'H'). He wishes to take a photograph by lining up his cows in a row so that as many Guernsey cows as possible appear in the even‐numbered positions (positions 2, 4, 6, …). However, due to his inability to communicate well with his cows, his only method to try to improve the picture is to perform a reversal on a prefix of the cow lineup—specifically, he may choose any even number j (2 ≤ j ≤ N) and reverse the order of the first j cows. Note that reversing an even‐length prefix swaps the cows originally in odd positions of that prefix into even positions (and vice–versa).

Formally, let the cows be numbered 1…N. If no operation is applied the score is the number of indices i (with i even) for which the cow in position i is a Guernsey. If a reversal is performed on the first j cows, then for positions 1 ≤ i ≤ j the cow that ends up at position i is the one originally at position j–i+1 while positions j+1…N remain in their original order. In general, Farmer John may perform a sequence of such prefix reversals (each with an even length) and his final arrangement can be viewed as partitioning the lineup into several contiguous segments. In each segment that was reversed an even number of times the cows remain in their original order, while in a segment that is reversed an odd number of times the roles of odd and even positions (with respect to the original lineup) are swapped. In particular, if a segment [L,R] (with R–L+1 even) is not reversed (or reversed an even number of times) then its contribution to the score is

(F_0(L,R)=\sum_{i=L}^{R} \mathbf{1}{{i \mbox{ is even}}}\mathbf{1}{{\mbox{cow } i \mbox{ is } G}}),

whereas if that segment is reversed once (or an odd number of times) then its contribution is

(F_1(L,R)=\sum_{i=L}^{R} \mathbf{1}{{i \mbox{ is odd}}}\mathbf{1}{{\mbox{cow } i \mbox{ is } G}}).

Farmer John’s goal is to achieve an arrangement with the maximum possible score, and he wishes to do so using as few prefix reversals as possible. Your task is to compute the minimum number of prefix reversals required to achieve an arrangement with the maximum possible score.

Note: All formulas must be rendered in LaTeX. For example, the definitions above should be interpreted in LaTeX format.

inputFormat

The first line contains a single even integer N (2 ≤ N ≤ 2×10^5). The second line contains a string of length N consisting only of the characters 'G' and 'H', where 'G' denotes a Guernsey and 'H' denotes a Holstein.

outputFormat

Output a single integer: the minimum number of prefix reversals required to achieve an arrangement for which the number of Guernsey cows in even‐numbered positions is maximized.

sample

2
GH

1