Dolbear's Law

Interview

Time limit1sMemory limit1024 MB

Summary

Given a per-second record of chirps, find the fewest crickets that could explain it when each cricket chirps at a fixed period between a start and a stop.

Level: Medium4 of 10
Topics: Brute force, Implementation, Math
Solved: No attempts yet

Problem

Dolbear's law describes the relationship between the chirping of crickets and the surrounding temperature.

$T = (Count+37)\,^{\circ}\mathrm{F}$
$T$ : temperature in degrees Fahrenheit, $Count$ : number of times a cricket chirps in one minute

Yechan wants to check whether Dolbear's law is true by counting how many times crickets chirp over $N$ seconds. However, the chirps of several crickets overlap, so he cannot count them properly and gives up on the proof.

Instead, Yechan records the chirps at 1-second intervals for $N$ seconds and wants to find the minimum number of crickets that are chirping.

Every cricket follows these rules.

Each cricket starts chirping at some moment, then chirps once each time a period passes.
The period is a positive integer chosen freely, and every cricket has the same period.
Each cricket stops chirping at some moment and does not chirp after that.

Help Yechan find the minimum number of crickets $X$ that are chirping.

Input

The first line contains the measurement time $N$ .

The second line contains Yechan's record as a string of length $N$ , made only of . and #. A . means no cricket chirped at that second, and a # means at least one cricket chirped.

Output

Print the minimum number of crickets $X$ that are chirping on the first line.

Constraints

$10 \leq N \leq 2000$
The input string contains only . and #.

Examples2

Example 1
Input
```
20
..#..#..#..#..#..#..
```
Expected output
```
1
```
Example 2
Input
```
30
...#####.....#####.....#####..
```
Expected output
```
3
```