E: 往復文字列 / Round-trip String

物語

ここは全人類が競技プログラマーになった世界。この世界ではみなさんの生きる現代では考えられないような習慣が多数存在する。その中の一つに、両親、特に母親に感謝の証を表す時は、文字列を送るという風習がある。送る文字列としてどのような文字列がふさわしいかは地域差があるが、北の大地北海道では、できるだけシンプルな文字列が贈り物としてふさわしい。また、送られた側の母親は子供に返礼として、送られた文字列がどれほど美しいかを答える必要がある。

さて、今あなたは1児の母親から相談を受けている。その母親は子供から素晴らしそうな文字列をもらったのだが、どれくらい素晴らしいのかうまく測れないでいるそうだ。北海道の風習では、母親に送る文字列 T はある文字列 S を往復させて作ることになっている。この時、 S ができるだけ短い文字列ならばより素晴らしい文字列 T である。母親は子供の頑張りに報いるため、T を作ることができる文字列の中で、最短の文字列を見つけてあげたいが、それはなかなか難しいとのことだ。あなたのプログラミング能力を駆使して母親の悩みを解決して欲しい。

問題

長さが 2 以上の文字列 S から、以下のルールに従って長さ N の文字列 T を生成する。ここで、 S の文字列長を K とし、T[i] は文字列 T の i 番目の文字を表す。ここで、 T の先頭文字は 0 番目の文字とする。

T[i] = S[K - 1 - | (i $\bmod$ (2K - 2)) - K + 1 |]

T のみが与えられたとき、 T を生成する文字列は複数考えられる。 それらの文字列の中で最小の文字列長 K_{min} を出力せよ。

入力形式

N
T

制約

• 2 \leq N = |T| \leq 1,000,000
• 文字列は英小文字のみからなる

出力形式

T を生成する長さ最小の文字列 S の長さ K_{min} を出力してください。

入力例1

6
tabata

出力例1

3

入力例2

4
hcpc

出力例2

3

入力例3

60
aaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbb

出力例3

12