← 返回题目列表

AtCoder · joi2019_yo_c

C. Marubatsu 邮票(圆形十字邮票)

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

配点: 100 点

問題文

JOI 您有三种类型的印章:Maru 印章、Cross 印章和 Maru Batsu 印章。 0 。这些邮票可以在纸上打印圆圈和十字等标记。

当您使用火星印章时,火星 将打印 1 ,如果使用十字印章,则十字将被打印 将打印 1 。当您使用 Marubutsu 印章时,标记和十字会水平排列。 1 它们是一张一张打印的,通过更改图章的方向,您可以打印十字位于圆圈的右侧,或圆圈位于十字的右侧。

JOI,你有你所拥有的邮票。 1 我在一张纸上以水平线打印了圆圈和十字,每次都以适当的顺序使用它们。打印的圆圈和十字是字符串。 它由 S 表示。 由S 是 仅由 O 和 X 构造的长度 是一个字符串 N ,S_i = O 然后 JOI 从您打印的标记的左侧开始 代表第 i 个是一个圆,S_i = X 表示这是错误的(1 ≦ i ≦ N).

你不知道 JOI 有多少枚邮票,但你知道 JOI 打印了几排圆圈和十字。从一排印刷的圆圈和十字中,找出 JOI 拥有的十字标记的最大可能数量。

制約

  • 1 ≦ N ≦ 100000 (= 10^5)
  • S 是长度 它是一个 N 字符串。
  • S 中的每个字符是 O 或 X 。

入力

输入是按以下格式从标准输入给出的。

N
S

出力

JOI 输出您拥有的最大可能数量的 Marubatsu 印章。


入力例 1

5
OXXOX

出力例 1

2

JOI 您打印的标记从左到右依次是圆圈、十字、十字、圆圈和十字。 JOI 你有印章、十字印章、十字印章。 如果您有 0, 1, 2 ,则可以按以下顺序使用印章打印类似的标记。

  • 1 使用第二个十字印章按顺序打印一个圆圈和一个十字。
  • 在此右侧,2 使用第二个十字印章按顺序打印十字和圆圈。
  • 最后,使用十字印章在其右侧打印一个十字。

Marubatsu 邮票 我想不出你有超过 3 的情况,所以 输出2 。


入力例 2

14
OXOXOXOXXOXOXO

出力例 2

7

入力例 3

10
OOOOOOOOOO

出力例 3

0