### PROBLEM LINK:

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Longest Increasing subsequence.

### EXPLANATION

For each element of modified sequence we have bi >= i (1<=i<=n)

and we need to find the longest increasing subsequence of the original sequence ai and ai >= i.

We keep such ai unchanged and other values can be changed into the value as their index.

If we make another ci = ai - i, the answer is the equal to

(n - the longest of the non-decreasing subsequence with no negative number)

and for longest non-decreasing subsequence , a O(nlogn) solution can be used.