AtCoder Beginner Contest 023

B - 手芸王


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は趣味でアクセサリーを作っている。

アクセサリーは a, b, c のいずれか 1 文字が書かれたブロックを横 1 列に並べることで作成できる。

高橋君は、以下の手順でアクセサリーの作成を行う:

  • 手順 0 : 高橋君は b 1 文字からなるアクセサリーを作成する。

以降の手順では、既にあるアクセサリーの両端にブロックを 1 つずつ追加することでアクセサリーを改造する。

  • 手順 3n + 1 (n ≧ 0) : 手順 3n で完成したアクセサリーの左端に文字 a が書かれたブロックを、右端に文字 c が書かれたブロックを付け足す。
  • 手順 3n + 2 (n ≧ 0) : 手順 3n+1 で完成したアクセサリーの左端に文字 c が書かれたブロックを、右端に文字 a が書かれたブロックを付け足す。
  • 手順 3n (n ≧ 1) : 手順 3n-1 で完成したアクセサリーの左端に文字 b が書かれたブロックを、右端に文字 b が書かれたブロックを付け足す。

高橋君はアクセサリーの作成を好きな手順の直後に終了することができる。終了した場合、アクセサリーには、アクセサリーを構成するブロックに書かれた文字を左から右に読んだものと同じ名前が付けられる。

例えば、手順 0, 1, 2, 3 それぞれの直後にアクセサリーの作成を終了した場合、アクセサリーの名前は順に、b, abc, cabca, bcabcab となる。

文字列 S が与えられるので、その文字列がアクセサリーの名前として考えられるかを判定し、考えられるなら何番目の手順の直後にアクセサリーの作成を終了したのかを求めよ。


入力

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

N
S
  • 1 行目には、文字列 S の長さを表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目には、半角の小文字アルファベットのみからなる文字列 S が与えられる。

出力

文字列 S が手順 K の直後にアクセサリーの作成を終了したときのアクセサリーの名前と等しいような整数 K が存在する場合は整数 K を、いつアクセサリーの作成を終了してもアクセサリーの名前が S とならないときは -11 行に出力せよ。出力の末尾にも改行を入れること。


入力例1

3
abc

出力例1

1
  • 手順 1 の直後にアクセサリーの作成を終了したときのアクセサリーの名前は abc となる。

入力例2

6
abcabc

出力例2

-1
  • 文字列 abcabc はアクセサリーの名前として考えられない。

入力例3

7
atcoder

出力例3

-1
  • 文字列 S には a, b, c 以外の文字が入ることがある。

入力例4

19
bcabcabcabcabcabcab

出力例4

9

Submit提出する