今天马戏团将有一场不寻常的表演——仓鼠和老虎一起表演!它们都沿着竞技场边缘围成一圈,现在训练员面临着一项艰巨的任务:他要交换动物的位置,以便所有仓鼠站在一起,所有老虎也站在一起。训练师将动物成对交换,以免造成混乱。他命令两只动物走出圈子并交换位置。由于当老虎在附近时,仓鼠会感到非常不舒服,而当周围有太多潜在的猎物(不仅包括仓鼠,还包括美味的观众)时,老虎也会感到紧张,因此训练师希望花尽可能少的时间移动动物,即他希望通过最少的交换次数来实现这一目标。你的任务是帮助他。
输入
第一行包含数字 n (2 ≤ n ≤ 1000),表示竞技场中动物的总数。第二行包含动物位置的描述。该线由n个符号“H”和“T”组成。 “H”对应仓鼠,“T”对应老虎。保证竞技场上至少有一只仓鼠和一只老虎。动物按照它们在圆圈内的位置顺序给出,此外,最后一个动物站在第一个动物附近。
输出
打印单个数字,这是让培训师实现其目标的最小交换次数。
示例
输入 #1
3 HTH
输出 #1
0
输入 #2
9 HTHTHTHHT
输出 #2
2
注意
在第一个示例中,我们不应该移动任何人,因为每个物种的动物已经与其他物种分开。例如,在第二个示例中,您可以将位置 2 的老虎与位置 5 的仓鼠交换,然后将位置 9 的老虎与位置 7 的仓鼠交换。