Hoof, Paper, Scissors (Silver)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors".

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each other. They both count to three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors beats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut). For example, if the first cow makes a "hoof" gesture and the second a "paper" gesture, then the second cow wins. Of course, it is also possible to tie, if both cows make the same gesture.

Farmer John wants to play $N$ games of "Hoof, Paper, Scissors" against his prize cow, Bessie ($1 \le N \le 100{,}000$). Bessie is an expert at the game and can predict each of FJ's gestures before he makes it. Unfortunately, Bessie is also a cow, and a very lazy one. She tends to play the same gesture many times in a row. In fact, she is only willing to switch gestures at most once over the entire set of games. For example, she might play "hoof" for the first $x$ games, then switch to "paper" for the remaining $N-x$ games.

Given the sequence of gestures FJ will play, determine the maximum number of games that Bessie can win.

The first line contains $N$.

Each of the next $N$ lines contains one of FJ's gestures, in order. Each gesture is H, P, or S, meaning hoof, paper, or scissors.

Print the maximum number of games Bessie can win, given that she can change gestures at most once.