DOSA  Lalith Dosa
Lalith is going to have dinner and he has N dosas in front of him with their prices represented by sequence of integers a1, a2, a3 ... an.
And he has decided to eat in a different manner. You are free to replace the price of any dosa with any positive integer.
How many prices (integers) must be replaced to make the resulting sequence strictly increasing?
Input
The first line of the test case contains an integer N  the number of dosas.
The next line contains N space separated integers where the ith integer is ai, representing the price of the ith dosa.
Output
Output the minimal number of prices(integers) that should be replaced to make the sequence strictly increasing.
Constraints
0 < N <= 10^6
0 < ai <= 10^9
Sample Input #1
6
1 7 10 2 20 22
Sample Output #1
1
Sample Input #2
5
1 2 2 3 4
Sample Output #2
3
Explanation
In the first sample input, we can replace 2 with any integer between 11 and 19 to make the price sequence strictly increasing, hence the output is 1.
In the second sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the price sequence.
hide comments
rangey_18o3_20:
20210907 19:33:14
Read about longest nondecreasing sequence 

karthik1997:
20171228 19:40:11
Very Good Problem, Learnt something New :) 

shreynik kumar:
20160717 22:20:49
Hint : LIS + binary search


vaishnavi95:
20160616 14:02:16
id 17120850 can i know which test case my submission fails 

Shubham Aggarwal:
20151230 22:30:46
submissionid 15976937


anurag garg:
20140302 12:51:34
O(N LOG(N)) will pass 

Bhavik:
20140302 09:16:38
finally got it:) 

gyosh:
20140208 01:38:17
Be careful with case like:


Aravindan Chandrasekaran:
20140212 12:54:26
Getting WA , explain why my code fails ?


Ketan Gupta:
20140208 01:38:28
[spoiler removed] Last edit: 20140117 18:10:30 
Added by:  Arun Lakshman 
Date:  20140109 
Time limit:  0.5s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 