class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int n = nums.size();
vector<int> above;
vector<int> inRange;
for(int i = 0; i < n; ++i) {
if(nums[i] > right) above.push_back(i);
else if(nums[i] >= left && nums[i] <= right) inRange.push_back(i);
}
int ret = 0;
for(int i = 0; i < n; ++i) {
int left, right;
auto it1 = lower_bound(inRange.begin(), inRange.end(), i);
if(it1 == inRange.end()) {
break;
}
left = *it1;
auto it2 = lower_bound(above.begin(), above.end(), i);
if(it2 == above.end()) {
right = n;
} else {
right = *it2;
}
if(right < left) {
i = right;
} else {
ret += right - left;
}
}
return ret;
}
};
// find the elements that are in the range
// 2-pointer: make sure at least one element in the range is in the range [i,j]
// for each i, find the right-most boundary(the first element above the required range)
// find the first element inside the range
// [2],1,4,[3]
// X X [X] X X X X X X
