incresing-weights

Rohan is out for shopping and he has instruction to  bring maximum things(in weight) as much as he can bring. He is given list of things and corresponding weights  to buy. Since he had just studied strictly increasing function in mathematics he thought to buy things in order such that next thing he buys is greater that previous one irrespective of what he was suppose to bring back home. Can you tell how many things of given weight rohan can change to get incresing weights ( or maximum sum)

INPUT

First line contains N no of things Rohan need to buy

Next line contains weights of N things

OUTPUT

Print  minimum number of weights needed to change to make it strictly increasing weights to bring back home

CONSTRAINTS

0 < N ≤ 10^6

0 < weights ≤ 10^9

EXAMPLE 1

INPUT

4

10 20 30 40

OUTPUT

0

EXAMPLE 2

INPUT

7

2 9 12 3 29 35 41

OUTPUT

1

EXPLANATION

In example 1, no need to change anything as weights are in increasing order. So Output is 0.

In example 2, only number 3 needs to be changed or increased to number between 13 and 28 to make weights in increasing order. So Output is 1

SAMPLE INPUT
6
9 10 10 11 11 12

SAMPLE OUTPUT
4

Explanation

Last 4 numbers can be changed to make it strictly increasing that is 9 10 11 12 13 14. So Output is 4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: