// 演算法同 C 版：記憶化 DP，dp[i] = 從 i 出發最多造訪的索引數。
// Same algorithm as the C version: memoized DP, dp[i] = max indices visited from i.
// 兩側各掃 d 步，遇到 >= arr[i] 即停；答案是所有 dp[i] 的最大值。
// Scan d steps each side, stop at any height >= arr[i]; answer is max over all dp[i].

#include <vector>      // std::vector：可自動管理大小的動態陣列 / dynamic array that manages its own memory
#include <algorithm>   // std::max：回傳兩數中的較大者 / returns the larger of two values

class Solution {
public:
    int maxJumps(std::vector<int>& arr, int d) {
        int n = arr.size();                 // 陣列長度 / length of the array
        std::vector<int> memo(n, 0);        // 全部初始化為 0，代表「未計算」/ all zeros, meaning "not computed"

        int ans = 0;                        // 全域最大造訪數 / global best
        for (int i = 0; i < n; ++i)         // 以每個索引為起點 / try each index as a start
            ans = std::max(ans, dfs(i, arr, d, memo)); // 取較大者更新答案 / keep the larger
        return ans;
    }

private:
    // dfs 計算並快取 dp[i] / dfs computes and caches dp[i]
    int dfs(int i, std::vector<int>& arr, int d, std::vector<int>& memo) {
        if (memo[i] != 0) return memo[i];   // 已算過直接回傳（dp >=1，所以 0=未算）/ return cache (dp >=1, so 0 means unset)

        int n = arr.size();
        int best = 1;                       // 至少造訪自己 / at least visit i itself

        // 往右最多 d 步 / up to d steps to the right
        for (int x = 1; x <= d && i + x < n; ++x) {
            int j = i + x;
            if (arr[j] >= arr[i]) break;    // 障礙：跳不過或被擋 → 停止 / blocker: illegal or blocking → stop
            best = std::max(best, 1 + dfs(j, arr, d, memo)); // 取最長延伸 / take the longest extension
        }

        // 往左最多 d 步 / up to d steps to the left
        for (int x = 1; x <= d && i - x >= 0; ++x) {
            int j = i - x;
            if (arr[j] >= arr[i]) break;
            best = std::max(best, 1 + dfs(j, arr, d, memo));
        }

        return memo[i] = best;              // 一行內存入快取並回傳 / cache and return in one line
    }
};