標高の列 \(H=(H _ 1,H _ 2,\ldots,H _ N)\) について、このコースに高橋くんが恐怖を感じないことの必要十分条件を考えてみます。

\(H _ i-H _ {i+1}\lt K\) を変形すると、\[\begin{aligned}H _ i-H _ {i+1}\lt K&{}\iff H _ i-H _ {i+1}\le K-1\\&{}\iff H _ i\le H _ {i+1}+(K-1)\\&{}\iff H _ i+i(K-1)\le H _ {i+1}+(i+1)(K-1)\end{aligned}\] となります。 これが \(1\le i\lt N\) について成り立つことは、数列 \(H ^ \prime _ i=H _ i+i(K-1)\ (1\le i\le N)\) が単調非減少であることを意味します。

よって、次の問題を解ければよいです。

整数列 \(H ^ \prime=(H ^ \prime _ 1,H ^ \prime _ 2,\ldots,H ^ \prime _ N)\) が与えられる。\(H ^ \prime _ 1,H ^ \prime _ N\) 以外の要素をいくつ書き換えれば \(H ^ \prime\) を単調非減少にできるか。

\(H ^ \prime _ 1\gt H ^ \prime _N\) ならば、それ以外の要素をどれだけ書き換えても単調非減少にはなりません。 逆に、\(H ^ \prime _ 1\le H ^ \prime _ N\) ならば、いくつかの要素を書き換えることで単調非減少にすることができます（例えば、すべてを \(H ^ \prime _ 1\) に書き換えればよいです）。

書き換える要素の個数の最小化は、書き換えない要素の個数の最大化といえます。 書き換えなかった要素を \(H ^ \prime _ 1,H ^ \prime _ {i _ 1},H ^ \prime _ {i _ 2},\ldots, H ^ \prime _ N\ (1\lt i _ 1\lt i _ 2\lt\cdots\lt N)\) とします。 それ以外の要素を適切に書き換えた列が単調非減少であるので、この部分列も単調非減少であることが必要です。 逆に、これが成り立てばそれ以外の要素を適切に書き換えることで（例えば、書き換えない直前の要素の値にすることで）書き換えたあとの列を単調非減少にすることができます。

よって、書き換えない要素の個数の最大値は、\(H ^ \prime\) の単調非減少な部分列であって \(H ^ \prime _ 1,H ^ \prime _ N\) を含むものの長さの最大値となります。 これは、最長増加部分列を求めるのと似たようなアルゴリズムを用いることで \(O(N\log N)\) 時間で求めることができます。

以上より、この問題を解くことができました。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<long> H(N);
    for (long& h : H) {
        cin >> h;
    }

    // 「恐怖を感じない」を「H[i] + i * (K - 1) が単調非減少」に読み替え
    for (int i = 0; i < N; ++i) {
        H[i] += static_cast<long>(i) * (K - 1);
    }

    // 先頭が末尾より大きければ
    if (H[0] > H[N - 1]) {
        cout << -1 << endl; // どのように書き換えても不可能
        return 0;
    }

    // 最長増加部分列を求める DP
    vector<long> dp;
    for (int i = 1; i + 1 < N; ++i) {
        if (H[0] <= H[i] && H[i] <= H[N - 1]) {
            auto it = ranges::upper_bound(dp, H[i]);
            if (it == end(dp)) {
                dp.emplace_back(H[i]);
            } else {
                *it = H[i];
            }
        }
    }

    // 先頭と末尾と最長増加部分列の要素は書き換えなくていい
    cout << N - size(dp) - 2 << endl;
    return 0;
}

from bisect import bisect_right


N, K = map(int, input().split())

H = list(map(int, input().split()))

# 「恐怖を感じない」を「H[i] + i * (K - 1) が単調非減少」に読み替え
for i in range(N):
    H[i] += i * (K - 1)

# 先頭が末尾より大きければ
if H[0] > H[-1]:
    print(-1) # どのように置き換えても不可能
    exit()

# 最長増加部分列を求める DP
dp = []
for h in H[1:-1]:
    if H[0] <= h <= H[-1]:
        it = bisect_right(dp, h)
        if it == len(dp):
            dp.append(h)
        else:
            dp[it] = h

# 先頭と末尾と最長増加部分列の要素は書き換えなくていい
print(N - len(dp) - 2)