Незнайка и его друг Гунька играют в игру. Игра состоит из
N ходов. На каждом ходу каждый игрок играет одним из двух жестов, Камень и Бумага, как в «Камень-ножницы-бумага», при следующих условиях:
- После каждого хода
(количество раз, когда игрок играл Бумагу) <= (количество раз, когда игрок играл Камень).
- Счет каждого игрока рассчитывается по формуле:
(количество ходов, на которых игрок выигрывает) - (количество ходов, на которых игрок проигрывает),
где результат каждого хода определяется по правилам «камень-ножницы-бумага».
Для тех, кто не знаком с игрой "Камень-нужница-бумага": если один игрок играет Камень, а другой играет Бумагу, последний игрок выиграет, а первый проиграет. Если оба игрока играют одним и тем же жестом, раунд считается ничейным, и ни один из игроков ни выиграет ни проиграет.
Используя волшебную палочку Незнайка смог предвидеть жест, который Гунька будет использовать в каждом из
N ходов перед началом игры. Распланируйте жесты Незнайки на каждом шагу, чтобы максимизировать его счет.
Жест, который Гунька будет воспроизводить на каждом ходу, задается строкой
s. Если
i-й (1 <= i <= N) символ в
s равен
g, то Гунька будет играть "Камень" на
i-м ходу. Аналогично, если
i-й (1 <= i <= N) символ
s в
p, Гунька будет играть Бумага на
i-м ходу.
Входные данные
На вход подается одна строка
s длиной N. Каждый символ в строке
s - это
g или
p. Жесты, представленные
s, удовлетворяют условию игры.
Выходные данные
Выведите максимально возможный счет Незнайки.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
gpg |
0 |
Выполнение одного и того же жеста с противником на каждом этапе дает 0 очков, что является максимально возможным результатом. |
| 2 |
ggppgggpgg |
2 |
Например, рассмотрите возможность воспроизведения жестов в следующем порядке: Камень, Бумага, Камень, Бумага, Камень, Камень, Бумага, Бумага, Камень, Бумага. Эта стратегия приносит три победы и одно поражение, в результате чего получается 2, что является максимально возможным результатом. |