#527. Photoshoot B

Photoshoot B

题目描述

迫切希望在郡县集市上赢得最佳奶牛摄影师的 Farmer John 正在尝试为他的 NN 头奶牛拍摄一张完美的照片(2N21052 \leq N \leq 2\cdot 10^5NN 为偶数)。

Farmer John 拥有两种品种的奶牛:更赛牛(Guernsey)和荷斯坦牛(Holstein)。为了使他的照片尽可能地艺术,他想把他的奶牛排成一排,使得尽可能多的更赛牛处于队列中的偶数位置(队列中的第一个位置是奇数位置,下一个是偶数位置,以此类推)。由于他与他的奶牛缺乏有效的沟通,他可以达到目的的唯一方法是让他的奶牛的偶数长的「前缀」进行反转(一个前缀指的是对于某个位置 jj,从第一头奶牛到第 jj 头奶牛范围内的所有奶牛)。

请计算 Farmer John 达到目的所需要的最小反转次数。

输入格式

输入的第一行包含 NN 的值。

第二行包含一个长为 NN 的字符串,给出初始时所有奶牛从左到右的排列方式。每个 'H' 代表一头荷斯坦牛,每个 'G' 代表一头更赛牛。

输出格式

输出一行,包含达到目的所需要的最小反转次数。

14
GGGHGHHGHHHGHG
1

样例解释

在这个例子中,只需反转由前六头奶牛组成的前缀即可。

   GGGHGHHGHHHGHG (反转前)
-> HGHGGGHGHHHGHG (反转后)

在反转之前,四头更赛牛处于偶数位置。反转后,六头更赛牛处于偶数位置。不可能使得超过六头更赛牛处于偶数位置。

数据范围

  • 测试点 2-6 满足 N1000N\le 1000

  • 测试点 7-11 没有额外限制。