DOSA - Lalith Dosa

no tags 

 

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?

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 thr price of i-th 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 #01

6

1 7 10 2 20 22

Sample Output #01

1

 

Sample Input #02

5

1 2 2 3 4 

Sample Output #02

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
shreynik kumar: 2016-07-17 22:20:49

Hint : LIS + binary search

vaishnavi95: 2016-06-16 14:02:16

id 17120850 can i know which test case my submission fails

Shubham Aggarwal: 2015-12-30 22:30:46

submissionid 15976937
Can you tell me the test cases where it failed? T

Last edit: 2015-12-30 22:40:58
anurag garg: 2014-03-02 12:51:34

O(N LOG(N)) will pass

Bhavik: 2014-03-02 09:16:38

finally got it:)

gyosh: 2014-02-08 01:38:17

Be careful with case like:
12
10 11 12 10 9 15 16 22 21 19 20 21

the correct answer is 4.

Aravindan Chandrasekaran: 2014-02-12 12:54:26

Getting WA , explain why my code fails ?
Submission Id : 10895238

Ketan Gupta: 2014-02-08 01:38:28

[spoiler removed]

Last edit: 2014-01-17 18:10:30
vank: 2014-02-08 01:38:34

getting WA...
@arun lakshman can u provide test cases where it fails...
submission id:10840613

Last edit: 2014-01-11 08:26:55
Mitch Schwartz: 2014-02-06 14:37:52

@Ashwini: "You are free to replace the price of any dosa with any positive integer." So changing to zero is not allowed. (I know that in e.g. French the word that closely resembles "positive" includes zero, but that is not the case in English.)

Last edit: 2014-01-10 15:20:16

Added by:Arun Lakshman
Date:2014-01-09
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own