Minimum Modifications for Strictly Increasing Sequence

Given a sequence of numbers (A_1, A_2, \cdots, A_n), your task is to modify as few numbers as possible (by setting them to any real number) so that the resulting sequence becomes strictly increasing.

Note that originally the problem mentioned modifying the numbers to integers, but the intended correction is that the modified numbers can be any real numbers.

Observation: The optimal strategy is to leave unchanged a longest strictly increasing subsequence (LIS) and modify the remaining elements. Therefore, the answer is given by:
[ \text{answer} = n - |\text{LIS}|.]

Determine and print the minimum number of modifications required.

inputFormat

The first line contains an integer (n) representing the number of elements in the sequence.

The second line contains (n) space-separated numbers (A_1, A_2, \cdots, A_n).

outputFormat

Output a single integer — the minimum number of modifications required to make the sequence strictly increasing.

sample

5
4 1 5 2 6

2