Score : $300$ points

问题描述

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

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

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

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

• 字符串 $S$ 中存在一个连续子串，它是级别为 $X$ 的团子串。

如果没有这样的整数，请输出 -1。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:24:20