← 返回题目列表

Codeforces · 1082/B

B. Vova 和奖杯

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

Vova 在不同的比赛中赢得了 $$$n$$$ 奖杯。每个奖杯都是金色或银色的。奖杯排列成一排。

排列的美妙之处在于由金色奖杯组成的最长子段的长度。 Vova 希望交换两个奖杯(不一定是相邻的奖杯),以使排列尽可能美观 - 这意味着,最大化此类最长子段的长度。

帮助 Vova!告诉他,如果允许他最多进行一次交换,那么这种安排可能会尽可能美丽。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 奖杯数量。

第二行包含$$$n$$$个字符,每个字符要么是G,要么是S。如果第$$$i$$$个字符是G,则第$$$i$$$个奖杯是金色奖杯,否则是银色奖杯。

输出

如果允许 Vova 最多进行一次交换,则打印金色奖杯子段的最大可能长度。

示例

输入 #1

10
GGGSGGGSGG

输出 #1

7

输入 #2

4
GGGG

输出 #2

4

输入 #3

3
SSS

输出 #3

0

注意

在第一个示例中,Vova 必须交换索引为 $$$4$$$ 和 $$$10$$$ 的奖杯。这样他就得到了序列“GGGGGGGSGS”,金色奖杯的最长子段长度为$$$7$$$。

在第二个示例中,Vova 根本无法进行交换。序列中最长的金色奖杯子段的长度为 $$$4$$$。

在第三个示例中,Vova 无法执行任何操作来使序列中金色奖杯的最长子段的长度大于 $$$0$$$。