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.