上完一天的课，小 Z 不但没有一丝疲惫感，反而觉得浑身是劲，好象又回到了童年， 他蹦蹦跳跳地回到家，吃过晚饭很快就做完了作业，抬头一看觉得房间太乱了，这不进入 初三后由于课业繁重一直没时间整理房间，现在有空了是时候该好好整理一下了。小 Z 首 先想要整理的是他那些心爱的奖牌，这些奖牌记录了小 Z 成长的足迹，其中有龙城少儿围 棋比赛的银牌，有华罗庚杯少年数学邀请赛的铜牌，份量最重的当数全国信息学奥林匹克 竞赛（National Olympiad in Informatics,简称 NOI）的金牌，小 Z 喜欢把他获得的奖牌 都挂在床头，并且成一字排开状，他每得到一枚奖牌就会在床头钉一颗钉子，将这枚奖牌 挂在所有奖牌的未尾，也就是说小 Z 的奖牌是按获得时间的先后顺序来排列的，现在小 Z 想把它们按金银铜的顺序排列，即所有的金牌挂在最前面，随后是银牌，最后是铜牌。小 Z 重排奖牌的方法很特别，他每次都是同时伸出双手各摘下一块奖牌，然后把这两块奖牌 的位置对换一下，即左手摘下的奖牌放到右手摘下的奖牌的位置，右手摘下的奖牌放到左手摘下的奖牌的位置，咦！这怎么看上去有点象交换赋值，太有才了！现在小 Z 想考考你， 给定奖牌序列，计算最少需要几次对换操作就可以将所有奖牌按金银铜牌的顺序排好。

输入数据第一行只有一个正整数 N 表示奖牌序列的长度，其中 1≤N≤1000；

输出数据仅有一行包含一个整数，表示最少需要几次对换操作。

【样例解释】
S    S    S＜  G    G
S＜  G    G    G    G
G＜  S    S    S    S
B    B＜  S    S    S
B    B    B    B＜  S
B    B    B    B    B
S    S＜  B    B    B
B    B    B    B    B
G    G    G＜  S＜  B
小Z的床头共有9枚奖牌，以上数据第一列为9枚奖牌的初始序列，每次操作将每列中箭头指向的两个位置的奖牌对换，对换后变成右边一列的状态，经过4次对换操作所有奖牌就按金银铜牌的顺序依次排好了，可以验证4步操作是必不可少的。
 
【数据范围】
10%的数据满足：奖牌种类只有两种
30%的数据满足：n≤10
60%的数据满足：n≤100
100%的数据满足：n≤1000

【来源】
常州市2014“信息与未来”选拔赛

市赛 字符串

市赛字符串