LC2444

class Solution {
    using ll = long long;
    vector<int> nextMink;
    vector<int> nextMaxk;
    vector<int> cutoff;

    ll calc(int beg, int end) {
        if (beg >= end) return 0;
        int n = max(nextMink[beg], nextMaxk[beg]);
        if (n >= end) return 0;
        return end - n;
    }
public:
    long long countSubarrays(vector<int>& ns, int minK, int maxK) {
        ll ret = 0;

        for (int i = 0; i < ns.size(); ++i) {
            if (ns[i] > maxK || ns[i] < minK) cutoff.push_back(i);
        }
        nextMink = vector<int>(ns.size());
        nextMaxk = vector<int>(ns.size());
        int last_mink = INT_MAX, last_maxk = INT_MAX;
        for (int i = ns.size() - 1; i >= 0; --i) {
            if (ns[i] == minK) last_mink = i;
            if (ns[i] == maxK) last_maxk = i;
            nextMink[i] = last_mink;
            nextMaxk[i] = last_maxk;
        }
        cutoff.push_back(ns.size());
        for (int i = 0, j = 0; i < ns.size(); ++i) {
            if (i != cutoff[j]) {
                ret += calc(i, cutoff[j]);
            } else {
                ++j;
            }
        }
        return ret;
    }
};