102992: [Atcoder]ABC299 C - Dango

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

问题描述

对于正整数$L$，一个级数为$L$的团子字符串是一个满足以下条件的字符串。

• 它的长度为$L+1$，由o和-组成。
• 第一个字符和最后一个字符中恰好有一个是-，而其他$L$个字符是o。

例如，ooo-是一个级数为3的团子字符串，但-ooo-、oo和o-oo-都不是团子字符串（更准确地说，它们都不是任何正整数$L$的级数为$L$的团子字符串）。

给你一个长度为$N$的由两个字符o和-组成的字符串$S$。 找出满足以下条件的最大正整数$X$。

• 在$S$中有一个连续子串是级数为$X$的团子字符串。

如果没有这样的整数，打印-1。

约束

• $1\leq N\leq 2\times10^5$
• $S$是一个长度为$N$的由o和-组成的字符串。

输入

输入将从标准输入以以下格式给出：

$N$
$S$

输出

打印满足条件的最大的正整数$X$，使得$S$包含一个级数为$X$的团子字符串，如果不存在这样的整数，则打印-1。

样例输入1

10
o-oooo---o

样例输出1

4

例如，对应于$S$的第3个到第7个字符的子串oooo-是一个级数为4的团子字符串。 $S$中没有级数为5或以上的团子字符串，所以你应该打印4。

样例输入2

1
-

样例输出2

-1

只有空字符串和-是$S$的子串。 它们不是团子字符串，所以你应该打印-1。

样例输入3

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

样例输出3

7