478. Fewest Changes to Make It Increasing

One operation replaces any element with any integer, positive or negative. Print the fewest operations needed to make the array STRICTLY increasing.

1 5 3 4 -> 1 change the 5 to something below 3, such as 2 3 2 1 -> 2 only one element can be kept

Counting the changes directly is awkward, so count what you KEEP instead and subtract. Minimising changes is maximising the number of untouched elements.

## When a set of keepers is legal

Suppose indices i < j are both kept, with no kept index between them. The j - i - 1 positions between them must be filled with strictly increasing integers strictly between a[i] and a[j]. That is possible exactly when

a[j] - a[i] >= j - i

There are j - i - 1 slots and the values must all differ by at least 1, so the gap has to be at least j - i.

Nothing constrains the ends. Before the first keeper any number of strictly increasing integers below a[i] is available because integers run downward without limit, and the same holds after the last.

## The transform

Rewrite the condition:

a[j] - a[i] >= j - i becomes a[j] - j >= a[i] - i

So set b[i] = a[i] - i. A set of keepers is legal exactly when the corresponding b values are NON-DECREASING.

The largest legal set of keepers is therefore the longest non-decreasing subsequence of b, and

answer = n - (length of the longest non-decreasing subsequence of b)

Every trace of the original problem is gone. That is what makes this worth studying: the work was entirely in finding the right thing to measure.

## Non-decreasing, not increasing

b is compared with <=, not <. The original values are strictly increasing but the index subtraction absorbs exactly the strictness, so equal b values are legal and correspond to consecutive kept indices differing by exactly the index gap.

4 2 4 5 6 is the test for this. It answers 1: b is 4 1 2 2 2, whose longest non-decreasing subsequence is 1 2 2 2 of length 4. With strict comparison that drops to 2 and the answer comes out as 3.

## Cost

The O(n^2) version is a direct double loop. For n = 200000 use the patience scan: keep the list of smallest achievable tails and place each b[i] with an UPPER-bound binary search, which is what admits the equal case. A lower-bound search there silently computes the strictly increasing version.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`