B - 花壇の水やり 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は一列に並んだ花壇の管理を任されています。花壇には N 個の区画が左から右へ一列に並んでおり、それぞれの区画には花が植えられているか、空いているかのどちらかです。左から i 番目の区画を区画 i と呼びます (1 \leq i \leq N)。

花壇の状態は長さ N の文字列 S で表されます。S の i 文字目 (1 \leq i \leq N) が o のとき区画 i には花が植えられており、. のとき区画 i は空です。

高橋君はスプリンクラーを使って水やりをします。スプリンクラーは区画 1 に固定されており、1 以上 N 以下の整数 K を1つ選んで設定します。スプリンクラーを動かすと、区画 1 を起点として間隔 K で等間隔に水をまきます。すなわち、水がまかれる区画は区画 1, 1+K, 1+2K, \ldots のうち区画番号が N 以下であるものすべてです。

水をまいた区画に花が植えられている場合、その花は水やりされます。空の区画に水をまいても何も起こりません。高橋君は K の値を1つだけ選び、その設定でスプリンクラーを1回だけ動かします。K の値を最適に選ぶことで、水やりされる花の数を最大化したいと考えています。

水やりされる花の数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • S は長さ N の文字列であり、o と . のみからなる。

入力

N
S
  • 1 行目には、花壇の区画数を表す正の整数 N が与えられる。
  • 2 行目には、花壇の状態を表す長さ N の文字列 S が与えられる。S は o と . のみからなる。

出力

最適な K を選んだときに水やりされる花の数の最大値を 1 行で出力せよ。

入力例 1

10
o.o.o.o.o.

出力例 1

5

入力例 2

15
oo.oo.oo.oo.oo.

出力例 2

10

入力例 3

50
o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o.

出力例 3

17

Score : 300 pts

Problem Statement

Takahashi is in charge of managing a flower bed arranged in a row. The flower bed has N sections lined up in a row from left to right, and each section either has a flower planted in it or is empty. The i-th section from the left is called section i (1 \leq i \leq N).

The state of the flower bed is represented by a string S of length N. If the i-th character (1 \leq i \leq N) of S is o, then section i has a flower planted in it; if it is ., then section i is empty.

Takahashi waters the flowers using a sprinkler. The sprinkler is fixed at section 1, and he chooses and sets one integer K where 1 \leq K \leq N. When the sprinkler is activated, it sprays water at equally spaced intervals of K starting from section 1. Specifically, the sections that receive water are all sections among 1, 1+K, 1+2K, \ldots whose section numbers are at most N.

If a section that receives water has a flower planted in it, that flower is watered. Nothing happens if water is sprayed on an empty section. Takahashi chooses exactly one value of K and activates the sprinkler exactly once with that setting. He wants to maximize the number of flowers that are watered by optimally choosing the value of K.

Find the maximum number of flowers that can be watered.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • S is a string of length N consisting only of o and ..

Input

N
S
  • The first line contains a positive integer N, representing the number of sections in the flower bed.
  • The second line contains a string S of length N, representing the state of the flower bed. S consists only of o and ..

Output

Print in one line the maximum number of flowers that can be watered when the optimal K is chosen.

Sample Input 1

10
o.o.o.o.o.

Sample Output 1

5

Sample Input 2

15
oo.oo.oo.oo.oo.

Sample Output 2

10

Sample Input 3

50
o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o.

Sample Output 3

17