A - First ABC 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる長さ N の文字列 S が与えられます。
S の中で ABC が(連続な)部分文字列として初めて現れる位置を答えてください。すなわち、以下の条件を全て満たす整数 n のうち最小のものを答えてください。

  • 1 \leq n \leq N - 2
  • S の n 文字目から n+2 文字目までを取り出して出来る文字列は ABC である。

ただし、ABC が S に現れない場合は -1 を出力してください。

制約

  • 3 \leq N \leq 100
  • S は A, B, C からなる長さ N の文字列

入力

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

N
S

出力

S の中で ABC が部分文字列として初めて現れる位置を出力せよ。ただし、ABC が S に現れない場合は -1 を出力せよ。

入力例 1

8
ABABCABC

出力例 1

3

S の中で ABC が初めて現れるのは 3 文字目から 5 文字目までの位置です。よって 3 が答えになります。

入力例 2

3
ACB

出力例 2

-1

ABC が S に現れない場合は -1 を出力してください。

入力例 3

20
BBAAABBACAACABCBABAB

出力例 3

13

Score : 100 points

Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

  • 1 \leq n \leq N - 2.
  • The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

  • 3 \leq N \leq 100
  • S is a string of length N consisting of A, B, and C.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the position where ABC first appears as a substring in S, or -1 if it does not appear in S.

Sample Input 1

8
ABABCABC

Sample Output 1

3

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

13