C - Dango Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正の整数 L に対して、 レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。

  • o と - からなる長さ L+1 の文字列である。
  • 先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの L 文字はすべて o である。

例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません（より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません）。

2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。 次の条件を満たすような正整数 X のうち、最大のものを求めてください。

  • S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。

ただし、そのような整数が存在しない場合、-1 と出力してください。

制約

  • 1\leq N\leq 2\times10^5
  • S は o - からなる長さ N の文字列

入力

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

N
S

出力

S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。 そのような値が存在しない場合、-1 を出力せよ。

入力例 1

10
o-oooo---o

出力例 1

4

たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。 S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。

入力例 2

1
-

出力例 2

-1

S の連続する部分文字列は空文字列と - の 2 種類だけです。 これらはダンゴ文字列ではないため、-1 と出力してください。

入力例 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

出力例 3

7

Score : 300 points

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

  • It is a string of length L+1 consisting of o and -.
  • Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

  • There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

  • 1\leq N\leq 2\times10^5
  • S is a string of length N consisting of o and -.

Input

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

N
S

Output

Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7