Задача: Камень-Ножница-Бумага. Без "Ножниц"

Незнайка и его друг Гунька играют в игру. Игра состоит из N ходов. На каждом ходу каждый игрок играет одним из двух жестов, Камень и Бумага, как в «Камень-ножницы-бумага», при следующих условиях:
- После каждого хода
(количество раз, когда игрок играл Бумагу) <= (количество раз, когда игрок играл Камень).
- Счет каждого игрока рассчитывается по формуле:
(количество ходов, на которых игрок выигрывает) - (количество ходов, на которых игрок проигрывает),
где результат каждого хода определяется по правилам «камень-ножницы-бумага».

Для тех, кто не знаком с игрой "Камень-нужница-бумага": если один игрок играет Камень, а другой играет Бумагу, последний игрок выиграет, а первый проиграет. Если оба игрока играют одним и тем же жестом, раунд считается ничейным, и ни один из игроков ни выиграет ни проиграет.

Используя волшебную палочку Незнайка смог предвидеть жест, который Гунька будет использовать в каждом из N ходов перед началом игры. Распланируйте жесты Незнайки на каждом шагу, чтобы максимизировать его счет.
Жест, который Гунька будет воспроизводить на каждом ходу, задается строкой s. Если i-й (1 <= i <= N) символ в s равен g, то Гунька будет играть "Камень" на i-м ходу. Аналогично, если i-й (1 <= i <= N) символ s в p, Гунька будет играть Бумага на i-м ходу.

Входные данные
На вход подается одна строка s длиной N. Каждый символ в строке s - это g или p. Жесты, представленные s, удовлетворяют условию игры.

Выходные данные
Выведите максимально возможный счет Незнайки.
 

Примеры

Ваш ответ: