The Secret Room

Interview

Time limit2sMemory limit1024 MB

Summary

Given a sequence, find the length of the longest subsequence where every pair satisfies a_i - a_j < j - i.

Level: Medium6 of 10
Topics: Dynamic programming, Binary search, Array
Solved: No attempts yet

Problem

While solving another mystery of Gravity Falls, twins Dipper and Mabel had to enter a mysterious forest, where they came across an abandoned house deep in the woods. The house was very old, and the twins found nothing remarkable in it except a hidden room in the basement. The room was locked, and an intercom hung on the door.

Dipper was determined to open the room no matter what. This time he got lucky: on one page of his journal he found the key to the code that must be entered on the intercom. The journal recorded a sequence of numbers $a$ of length $n$ , and said that the code is the longest subsequence in which every pair of numbers satisfies $a_i - a_j < j - i$ . Help Dipper find the length of the code.

Input

The first line contains $n$ , the number of elements in the sequence ( $1 \le n \le 10^6$ ).

The next line contains the elements of the sequence, non-negative integers $a_i$ ( $1 \le a_i \le 10^9$ ).

Output

Print a single number: the number of values in the code that lets Dipper open the door of the secret room.

Hint

In the first test, $a_0 = 1, a_1 = 2, a_2 = 2$ . Checking all pairs shows that the inequality holds for each of them:

$a_0 - a_1 = 1 - 2 < 1 - 0$ .
$a_1 - a_2 = 2 - 2 < 2 - 1$ .
$a_0 - a_2 = 1 - 2 < 2 - 0$ .

In the second test, the inequality holds for the elements with indices 1, 2, 3, and 4. Any larger selection contains a pair for which the inequality fails.

Examples2

Example 1
Input
```
3
1 2 2
```
Expected output
```
3
```
Example 2
Input
```
6
5 3 5 6 6 5
```
Expected output
```
4
```