Use dynamic programming with Fenwick trees for range-maximum queries.

For every subsequence, track:

• Its last movement: up or down
• Whether the mulligan is still unused (0) or may have been used (1)

A transition to the current price x:

• Is an up-step when the previous price is at most x - M
• Is a down-step when the previous price is at least x + M
• May continue the same direction only by moving from a no-mulligan state to a mulligan state

python
import sys
from bisect import bisect_left, bisect_right


def solve(N: int, M: int, P: list[int]) -> int:
    if N == 0:
        return 0

    values = sorted(set(P))
    size = len(values)
    value_index = {value: i + 1 for i, value in enumerate(values)}

    # Fenwick trees for prefix maximum queries.
    #
    # Forward trees query previous values <= a limit.
    forward_up0 = [0] * (size + 1)
    forward_down0 = [0] * (size + 1)
    forward_down1 = [0] * (size + 1)

    # Reverse trees query previous values >= a limit.
    reverse_up0 = [0] * (size + 1)
    reverse_up1 = [0] * (size + 1)
    reverse_down0 = [0] * (size + 1)

    def query(tree: list[int], index: int) -> int:
        result = 0

        while index > 0:
            if tree[index] > result:
                result = tree[index]
            index -= index & -index

        return result

    def update(tree: list[int], index: int, value: int) -> None:
        while index <= size:
            if value > tree[index]:
                tree[index] = value
            index += index & -index

    answer = 1

    for price in P:
        # Previous price <= price - M creates an up-step.
        left_count = bisect_right(values, price - M)

        best_down0 = query(forward_down0, left_count)
        up0 = best_down0 + 1

        # Either:
        # 1. Alternate from down1 to up1, or
        # 2. Use the mulligan by going from up0 to up1.
        up1 = max(
            up0,
            query(forward_down1, left_count) + 1,
            query(forward_up0, left_count) + 1
        )

        # Previous price >= price + M creates a down-step.
        right_start = bisect_left(values, price + M)

        # In reversed coordinate order, this suffix becomes a prefix.
        reverse_count = size - right_start

        best_up0 = query(reverse_up0, reverse_count)
        down0 = best_up0 + 1

        # Either:
        # 1. Alternate from up1 to down1, or
        # 2. Use the mulligan by going from down0 to down1.
        down1 = max(
            down0,
            query(reverse_up1, reverse_count) + 1,
            query(reverse_down0, reverse_count) + 1
        )

        index = value_index[price]
        reverse_index = size - index + 1

        # Update only after calculating every state, so the current
        # element cannot transition to itself.
        update(forward_up0, index, up0)
        update(forward_down0, index, down0)
        update(forward_down1, index, down1)

        update(reverse_up0, reverse_index, up0)
        update(reverse_up1, reverse_index, up1)
        update(reverse_down0, reverse_index, down0)

        answer = max(answer, up1, down1)

    return answer


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))

    if len(data) < 2:
        return

    N = data[0]
    M = data[1]
    P = data[2:2 + N]

    print(solve(N, M, P))


if __name__ == "__main__":
    main()

Complexity

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