B - Shorten ARC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

A,R,C からなる長さ N の文字列 S が与えられます。

あなたは、S の中に隣接する 3 文字であって ARCとなっているものが存在する限り以下の操作を行うことができます。

  • 奇数 回目の操作では、S の中で隣接する 3 文字であって ARC となっているものを一つ選び、R で置き換える。

  • 偶数 回目の操作では、S の中で隣接する 3 文字であって ARC となっているものを一つ選び、AC で置き換える。

操作を行える回数の最大値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • S は A,R,C からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

6
AARCCC

出力例 1

2

以下のように操作すると、 2 回操作できます。

AARCCC → ARCC → ACC

入力例 2

5
AAAAA

出力例 2

0

S の中に隣接する 3 文字であって ARC となっているものが存在しないため、操作を一度も行えません。

入力例 3

9
ARCARCARC

出力例 3

3

Score : 400 points

Problem Statement

You are given a string S of length N consisting of A,R,C.

As long as S contains three consecutive characters that are ARC, you can perform the operation below.

  • In an odd-numbered (1-st, 3-rd, 5-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with R.
  • In an even-numbered (2-nd, 4-th, 6-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with AC.

Find the maximum number of operations that can be performed.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • S is a string of length N consisting of A,R,C.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

6
AARCCC

Sample Output 1

2

You can perform two operations as follows.

AARCCC → ARCC → ACC

Sample Input 2

5
AAAAA

Sample Output 2

0

S does not contain three consecutive characters that are ARC, so you cannot perform the operation at all.

Sample Input 3

9
ARCARCARC

Sample Output 3

3