POLICE

Problem

Over time, there have been many thefts and other incidents at universities, resulting in people wanting to increase security in these areas. For this reason, the government decided to establish the University Police. However, many members of the academic community, while agreeing that the areas need to be secured, believe that the solution chosen by the government is not the most appropriate. A few days before the arrival of the police at the Polytechnic University campus, you take on the difficult role of bridging the differences between the two sides. You are asked to write an algorithm that minimizes police presence at NTUA (National Technical University of Athens) while keeping it "safe".

The peripheral, circular road of the Polytechnic University campus has ~N~ guard posts in specific positions, numbered from ~1~ to ~N~. Due to the geometry of the road, if a police officer is placed at the ~i~-th guard post, they can see their own and the next ~k_i-1~ guard posts in a clockwise direction. You are asked to calculate the minimum number of police officers that must be placed at the guard posts so that all guard posts are supervised by a police officer.

Input:

The first line of the input will contain a positive integer ~N~, the number of guard posts. The next line contains ~N~ positive integers ~k_i~, the visibility of the ~i~-th guard post.

Output:

The output should contain one line with exactly one integer: the minimum number of police officers that must be placed so that all guard posts are supervised by someone.

Constraints

• ~1 \le N \le 1.000.000~
• ~1 \le k_i \le N~
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.

Examples of Input - Output files:

1st

STDIN (police.in)

3
2 1 3

STDOUT (police.out)

1

Explanation of the first example

From guard post ~3~, a police officer can see all the guard posts.

2nd

STDIN (police.in)

4
1 1 1 2

STDOUT (police.out)

3

Explanation of the second example

We place a police officer at guard post ~2~ and another at guard post ~3~, each of whom can only supervise their own guard post. Finally, we place a police officer at guard post ~4~, who will supervise guard posts ~4~ and ~1~.

3d

STDIN (police.in)

8
1 5 1 4 3 2 1 5

STDOUT (police.out)

2

Notes

• For test cases with a total value of ~10%~, it will be ~1 \le N \le 15~
• For test cases with a total value of ~20%~, it will be ~1 \le N \le 2000~ and ~1 \le k_i \le 50~
• For test cases with a total value of ~20%~, it will be ~1 \le N \le 5000~