Description

Given numbers $A_1, A_2, \cdots, A_n$, modify the fewest elements (to real values) so that the sequence becomes strictly increasing.

Note: The original statement mistakenly said to modify to integers; it has now been corrected to real numbers. The testdata ensures that the integer approach would also AC (it just cannot pass the sample).

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $A_1, A_2, \cdots, A_n$.

Output Format

Output one integer, the minimum number of elements to modify.

3
1 3 2

1

8
1 2 3 4 4 5 6 7

1

Hint

• Constraints:
  • For 50% of the testdata, $N \le 10^3$.
  • For 100% of the testdata, $1 \le N \le 10^5$, $1 \le A_i \le 10^9$.

Translated by ChatGPT 5