975

class Solution {
public:
    int oddEvenJumps(vector<int>& arr) {
        // Sort the array in ascending order.
        vector< pair<int, int> > narr;
        for(int i=0; i<arr.size(); i++)
            narr.push_back({arr[i], i});
        sort(narr.begin(), narr.end());

        // Find next higher using monotonic stack.
        vector<int> s;
        vector<int> next_higher(arr.size(), -1);
        for(auto p: narr){
            while(!s.empty() && s.back() < p.second){
                next_higher[s.back()] = p.second;
                s.pop_back();
            }
            s.push_back(p.second);
        }

        // Sort in descending order.
        narr.clear();
        for(int i=0; i<arr.size(); i++)
            narr.push_back({-arr[i], i});
        sort(narr.begin(), narr.end());

        // Find next lower using monotonic stack.
        s.clear();
        vector<int> next_lower(arr.size(), -1);
        for(auto p: narr){
            while(!s.empty() && s.back() < p.second){
                next_lower[s.back()] = p.second;
                s.pop_back();
            }
            s.push_back(p.second);
        }

        // Use boolean dp to store if we can jump upto last index.
        int sz = arr.size();
        bool dp[sz][2];
        memset(dp, 0, sizeof(dp));
        dp[sz-1][0] = true;
        dp[sz-1][1] = true;

        for(int i=sz-2; i>=0; i--){
            if(next_higher[i] != -1)
                dp[i][0] = dp[next_higher[i]][1];
            if(next_lower[i] != -1)
                dp[i][1] = dp[next_lower[i]][0];
        }
        int ans = 0;
        for(int i=0; i<sz; i++){
            if(dp[i][0]) ans++;
        }
        return ans;
    }
};