Dunno and his friend Gunka are playing a game. The game consists of
N moves. On each turn, each player plays one of the two gestures, Rock and Paper, as in Rock-Paper-Scissors, under the following conditions:
- After each move
(number of times the player played Paper) <= (number of times the player played Rock).
- The score of each player is calculated by the formula:
(number of turns the player wins) - (number of turns the player loses),
where the result of each move is determined by the rules of "rock-paper-scissors".
For those unfamiliar with the Rock-Paper-Tailing game, if one player plays Rock and the other plays Paper, the last player wins and the first player loses. If both players play with the same gesture, the round is considered a draw and neither player wins or loses.
Using a magic wand Dunno was able to foresee the gesture that Gunka would use in each of the
N moves before the start of the game. Plan out Dunno's gestures at every turn to maximize his score.
The gesture that Gunka will play on each move is specified by the
s string. If
i-th (1 <= i <= N) character in
s is equal to
g, then Gunka will play "Stone" on
ith move. Similarly, if the
i-th (1 <= i <= N) character
s in
p, Gunka will play Paper on < code>i-th move.
Input
The input is one string
s of length N. Each character in the string
s is
g or
p >. The gestures represented by
s satisfy the game condition.
Imprint
Print the maximum possible score of Dunno.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
gpg |
0 |
Performing the same gesture with an opponent in each step is worth 0 points, which is the maximum possible result. |
| 2 |
ggppgggpgg |
2 |
For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy yields three wins and one loss, resulting in 2, which is the highest possible score. |