Farmer John, desperate to win the award for best cow photographer at the county fair, is trying to take the perfect photograph of his ~N~ cows.

Farmer John owns cows of two potential breeds: Guernseys and Holsteins. To make his photo as aesthetic as possible, he wants to line up his cows so that as many Guernseys as possible are in even-numbered positions in the line. The first position is odd, the second is even, and so on.

Due to his lack of strong communication with his cows, the only way he can change the lineup is by asking an even-length prefix of cows to reverse itself. If he chooses some even ~j~, then the cows in positions ~1~ through ~j~ reverse their order.

Compute the minimum number of reversals required for Farmer John to maximize the number of Guernseys in even positions.

Input

The first line contains ~N~.

The second line contains a string of length ~N~ describing the cows from left to right. Each H represents a Holstein, and each G represents a Guernsey.

Output

Output the minimum number of reversals needed on a single line.

Constraints

• ~2 \le N \le 2 \cdot 10^5~
• ~N~ is even

Example 1

Input

14
GGGHGHHGHHHGHG

Output

1

Explanation

It suffices to reverse the prefix consisting of the first six cows:

GGGHGHHGHHHGHG
HGHGGGHGHHHGHG

Before the reversal, four Guernseys were in even positions. After the reversal, six Guernseys are in even positions, and this is optimal.