题目描述

最近小L在steam上玩一款叫做《冒险公社》的游戏，这是一款在线桌游，玩家要在一连串接踵而来的岛屿冒险中选择最优的策略，在保证安全的前提下赚取尽可能多的金币。

该游戏的地图可以视作$n$座连续的岛屿，玩家从第一座岛屿出发，依次经过所有岛屿最终到达第$n$座岛屿。岛屿有三种类型，分别为象征财富的绿岛（用$G$表示）、象征敌人的红岛（用$R$表示）与象征灾难的黑岛（用$B$表示）。

玩家手中还有一个可以预测岛屿颜色的罗盘，该罗盘也可以发出绿色$（G）$、红色$（R）$、黑色$（B）$三种颜色，其预测的规则是：玩家在第$i(3≤i)$座岛屿上时，若$i$、$i-1$、$i-2$三座岛中绿岛数量多于红岛则发绿光、若红岛数量多于绿岛则发红光、若两者数量相等则发黑光。

现在，给定罗盘对某一张游戏地图的全部预测结果，请你告诉渴望财富的小L，这张地图最多有多少个绿岛。

输入格式

输入第一行包括一个整数$n(3≤n≤10^5)$，岛的总个数。

第二行是一个长为$n$的字符串$S$，表示罗盘对该地图的预测结果，之中第$i$个字符表示罗盘在第$i$座岛时发出的光。保证$S_1 = S_2 = X$,表示在前两座岛上时罗盘无法预测，且保证在字符串中的其他字符一定是$RGB$三者之一。

输出格式

输出一个整数，表示在满足罗盘预测的前提下，这张地图最多有多少绿岛。特别地，若不存在一个满足罗盘预测的地图，输出$−1$。

样例

10 
XXGGGGGBGB

7

10 
XXBBBBBBRG

4

提示

by 励翔