Problem Description

Kirigiris and Slowlorises lined up in a queue to buy a Christmas cake.

According to a Tourist who observed them, the following information is known:

• A total of $ N $ animals lined up in order.
• Each animal in the queue is either a Kirigiri or a Slowloris.
• The $ i $-th animal that came and lined up skipped exactly $ A_i $ animals.
• A Slowloris never skipped another Slowloris.

How many Slowlorises are there in the queue at most?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the maximum number of Slowlorises that could be in the queue.

Sample Input and Output

Sample Input #1

3
0 0 1

Sample Output #1

2

Sample Input #2

4
0 1 2 3

Sample Output #2

1

Sample Input #3

7
0 0 1 0 0 2 4

Sample Output #3

4

Notes/Hints

Constraints

• $1 \leq N \leq 300,000$
• $0 \leq A_i \leq i-1$

Sample Explanation 1

In this input, only the 3rd animal skipped the 2nd animal. Therefore, it is impossible for both the 2nd and 3rd animals to be Slowlorises, so there are at most 2 Slowlorises. Since it is possible for the 1st and 2nd animals to be Slowlorises, the answer is 2.

Sample Explanation 2

In this input, it is impossible for there to be more than 1 Slowloris.

见题面 Input 部分

见题面 Output 部分