← 返回题目列表

Codeforces · 46/C

C. 仓鼠和老虎

中文机器翻译题面 查看原题

今天马戏团将有一场不寻常的表演——仓鼠和老虎一起表演!它们都沿着竞技场边缘围成一圈,现在训练员面临着一项艰巨的任务:他要交换动物的位置,以便所有仓鼠站在一起,所有老虎也站在一起。训练师将动物成对交换,以免造成混乱。他命令两只动物走出圈子并交换位置。由于当老虎在附近时,仓鼠会感到非常不舒服,而当周围有太多潜在的猎物(不仅包括仓鼠,还包括美味的观众)时,老虎也会感到紧张,因此训练师希望花尽可能少的时间移动动物,即他希望通过最少的交换次数来实现这一目标。你的任务是帮助他。

输入

第一行包含数字 n (2 ≤ n ≤ 1000),表示竞技场中动物的总数。第二行包含动物位置的描述。该线由n个符号“H”和“T”组成。 “H”对应仓鼠,“T”对应老虎。保证竞技场上至少有一只仓鼠和一只老虎。动物按照它们在圆圈内的位置顺序给出,此外,最后一个动物站在第一个动物附近。

输出

打印单个数字,这是让培训师实现其目标的最小交换次数。

示例

输入 #1

3
HTH

输出 #1

0

输入 #2

9
HTHTHTHHT

输出 #2

2

注意

在第一个示例中,我们不应该移动任何人,因为每个物种的动物已经与其他物种分开。例如,在第二个示例中,您可以将位置 2 的老虎与位置 5 的仓鼠交换,然后将位置 9 的老虎与位置 7 的仓鼠交换。