class Solution {// MONOTONIC QUEUE
public:
long long continuousSubarrays(vector<int>& nums) {
int r=0,l=0;
long long ans=0;
deque<int> maxQ;
deque<int> minQ;
while(r<nums.size()){
while(!maxQ.empty() && maxQ.back()<nums[r]){
maxQ.pop_back();
}
maxQ.push_back(nums[r]);
while(!minQ.empty() && minQ.back()>nums[r]){
minQ.pop_back();
}
minQ.push_back(nums[r]);
while(maxQ.front()-minQ.front()>2){
if(maxQ.front()==nums[l]) maxQ.pop_front();
if(minQ.front()==nums[l]) minQ.pop_front();
l++;
}
ans+=r-l+1;
r++;
}
return ans;
}
};
/* class Solution {//MULTISET
public:
long long continuousSubarrays(vector<int>& nums) {
int rear=0;
long long res=0;
multiset<int>st;
for(int f=0;f<nums.size();f++){
st.insert(nums[f]);
while(st.size()>1 && *st.rbegin()-*st.begin()>2){//*st.rbegin() gives the value at end of st
st.erase(st.find(nums[rear]));
rear++;
}
res+=f-rear+1;
}
return res;
}
};
*/
//we can't useheap in this problem ,we need to use monotonic queue(not stack) bcoz things dont get deleted easily frm heap
//MYSOL (not working)
/* class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
int s = nums.size();
int j = 0;
long long res = 0;
while (j < s) {
queue<int> q;
priority_queue<int, vector<int>, greater<int>> min;
priority_queue<int, vector<int>, less<int>> max;
while (j < s && (max.empty() || nums[j] - max.top() < 2) && (min.empty() || nums[j] - min.top() < 2)) {
q.push(nums[j]);
max.push(nums[j]);
min.push(nums[j]);
j++;
while (!q.empty() && (!max.empty() && nums[j] - max.top() >= 2 || !min.empty() && nums[j] - min.top() >= 2)) {
if (!max.empty() && q.front() == max.top()) max.pop();
if (!min.empty() && q.front() == min.top()) min.pop();
q.pop();
}
}
res += q.size();
}
return res;
}
};
*/