Problem Statement

There is an array $A$ of $N$ elements. The $i$-th element of $A$ is a positive integer $A_i$.

In $1$ operation, you can change any element of $A$ to any positive integer.

You want to perform this operation some number of times to make $A$ strictly increasing.

Find the minimum number of operations required to make $A$ strictly increasing.

An array $A$ of $N$ elements is said to be strictly increasing if $A_1 \lt A_2 \lt \dots \lt A_{N-1} \lt A_N$.

Problem Statement (with Story)

Shiratei enjoys competitive programming as a hobby and spends day and night taking part in contests. Competitive programming contests invariably come with rating values.

There is an array $A$ of $N$ elements that records, in chronological order, the rating values resulting from Shiratei's participation in $N$ contests.
The rating value immediately after the end of the $i$-th contest is $A_i$.

Shiratei is frustrated that his rating has stagnated, so he has decided to manipulate and falsify the records so that they become strictly increasing.

In $1$ operation, he can choose any $1$ of the $N$ rating value records and falsify it to any positive integer.
He intends to perform the operation some number of times to falsify the records so that the rating values are strictly increasing when viewed in chronological order.
Find the minimum number of operations required.

The rating values are said to be strictly increasing when viewed in chronological order if $A_1 \lt A_2 \lt \dots \lt A_{N-1} \lt A_N$.

Input

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

$1 \le N \le 2 \times 10^5$
$1 \le A_i \le 10^9$
All input values are integers.

Output

Output the answer in 1 line.
Print a newline at the end.

Sample

6
1 1 4 5 1 4

3

9
333333333 111111111 444444444 111111111 555555555 999999999 222222222 666666666 555555555

5

20
99922 3916262 22 35176942 700 7841 2792958 812325 516 15108 68477 4892660 894 84778 1537710 31499 5844 93505127 493351 815

12