Overview

By transforming the condition “you must not descend by \(K\) or more” in each move, the problem reduces to requiring that a certain transformed sequence is non-decreasing.
Then the problem becomes “maximize the number of points we can keep unchanged,” which ultimately requires finding the Longest Non-Decreasing Subsequence (LNDS).

Analysis

First, let’s rewrite the condition for not feeling fear into a more manageable form.

The condition for not feeling fear when moving from point \(i\) to \(i+1\) is:

\(H_i' - H_{i+1}' < K\)

Since we’re dealing with integers, this is equivalent to:

\(H_i' - H_{i+1}' \le K-1\)

Let us define:

\(D = K-1\)

1. Key Transformation

For the height \(h_i'\) at each point, consider the value:

\(A_i = h_i' + D(i-1)\)

Then the condition:

\(h_i' - h_{i+1}' \le D\)

becomes:

\(h_i' + D(i-1) \le h_{i+1}' + Di\)

which is:

\(A_i \le A_{i+1}\)

---

In other words, “not feeling fear” is exactly equivalent to the transformed sequence \(A_1, A_2, \dots, A_N\) being non-decreasing.

2. What conditions must unchanged points satisfy?

If point \(i\) is not changed, its transformed value is fixed at:

\(A_i = H_i + D(i-1)\)

Also, since the endpoints cannot be changed:

• \(A_1 = H_1\)
• \(A_N = H_N + D(N-1)\)

are fixed.

For the entire sequence to be non-decreasing, the \(A_i\) values of the unchanged points must satisfy:

1. They are non-decreasing when arranged in order
2. Since they must fit between the endpoints: \(A_1 \le A_i \le A_N\)

Therefore, the maximum number of interior points that can remain unchanged equals:

• Among the values \(A_i = H_i + D(i-1)\) for interior points
• Considering only those satisfying \(A_1 \le A_i \le A_N\)
• The length of their longest non-decreasing subsequence

3. Why is it sufficient to only look at subsequences?

You might wonder: “If the subsequence is non-decreasing, can we really fill in the other points by changing them appropriately?”

This is indeed possible.
Looking at the kept points (including endpoints) from left to right, if their transformed values satisfy:

\(a_{p_1} \le a_{p_2} \le \cdots\)

then for the changed points in between, we can freely assign values that fall within this range.
The original heights can be recovered as \(h_i' = A_i - D(i-1)\), and can be made non-negative integers.

Therefore, “it is sufficient for the kept points to form a non-decreasing subsequence.”

4. Impossibility Check

Even if we change all interior points, the endpoints are fixed.
Therefore, if:

\(A_1 \le A_N\)

does not hold, it is absolutely impossible.

This means:

\(H_1 \le H_N + D(N-1)\)

i.e.,

\(H_1 - H_N \le (K-1)(N-1)\)

If this is not satisfied, the answer is -1.

5. A naive solution is too slow

Finding the longest non-decreasing subsequence with a straightforward DP is \(O(N^2)\), which is too slow for \(N \le 3\times 10^5\).

Therefore, we use the \(O(N \log N)\) LNDS via patience sorting.

The key point here is that since we want “non-decreasing,” we use bisect_right for the binary search.
(Using bisect_left would give us “strictly increasing” instead.)

Algorithm

1. Set \(D = K-1\).
2. Compute the transformed values at the endpoints:
   • \(\text{lo} = H_1\)
   • \(\text{hi} = H_N + D(N-1)\)
3. If \(\text{lo} > \text{hi}\), it is impossible, so output -1.
4. For each interior point \(i=2,\dots,N-1\), compute
   \(x = H_i + D(i-1)\).
5. Extract only those \(x\) satisfying \(\text{lo} \le x \le \text{hi}\), and find the length \(L\) of the longest non-decreasing subsequence of that sequence.
6. Since there are \(N-2\) interior points in total, the answer is:

\(N-2-L\)

How to compute LNDS

Maintain tails[len] as:
“The minimum possible last element of a non-decreasing subsequence of length len+1.”

For each \(x\):

• Compute j = bisect_right(tails, x)

Then:

• If j == len(tails), append to the end
• Otherwise, set tails[j] = x

The final len(tails) is the length of the LNDS.

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since we want a “non-decreasing subsequence,” use bisect_right for the binary search.

• Note that the transformed value is: \(A_i = H_i + (K-1)(i-1)\)

• Interior points that do not satisfy lo <= x <= hi cannot be included in a non-decreasing sequence containing the endpoints, so they can be ignored.

• The same code works even for \(N=2\). Since there are \(0\) interior points, the answer is 0 if it is possible.

  Source Code

import sys
from bisect import bisect_right

def solve():
    vals = list(map(int, sys.stdin.buffer.read().split()))
    N, K = vals[0], vals[1]
    D = K - 1

    lo = vals[2]                  # H_1 + D*0
    hi = vals[N + 1] + D * (N - 1)  # H_N + D*(N-1)

    if lo > hi:
        print(-1)
        return

    tails = []
    for i in range(1, N - 1):
        x = vals[2 + i] + D * i
        if lo <= x <= hi:
            j = bisect_right(tails, x)
            if j == len(tails):
                tails.append(x)
            else:
                tails[j] = x

    print(N - 2 - len(tails))

if __name__ == "__main__":
    solve()

---

This editorial was generated by gpt-5.4-high.