C++ Solution | Monotonic Stack modification
This appraoach is a modification Of monotonic stack to store the Previous Greater Element(pge) - (stored in vector named left) and Next Greater Element (nge) fo
This appraoach is a modification Of monotonic stack to store the Previous Greater Element(pge) - (stored in vector named left) and Next Greater Element (nge) for every element(stored in vector named right).\nFor any element i, it forms a part of valid subarrays till it encounters it\'s next greater elements from the left as well as the right side, that is, we count the number of subarrays for a particular i for which that element would be the maximum element. The size of the subarray is calculated as ```(i-left[i])*(right[i]-i)``` \nFor example, in the example [2,1,4,3]:-\n1. 2 lies in the given raneg [L,R) and The previous greater element for 2 does not exist i.e. left = -1 and the next greater element is at index 3. Hence number of subarrays **including 2 as the maximum element** become (0-(-1))*(3-0)  = 3.\n2. Similarly we calculate number of subarrays for every index i (if nums[i] lies in the range).\nYou can read more about Monotonic Stacks on this great discuss post [https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step] \n\nCode implementing the same is:-\n```\nclass Solution {\npublic:\n    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {\n        \n        int n = A.size();\n\n        stack<int> pge,nge; //Previous greater element(pge) and Next Greater element(nge)\n        vector<int> left(n,-1);//Stores PGE for index i\n        vector<int> right(n,n);//Stores NGE for index i\n        int ans= 0;\n        for(int i=0;i<n;++i)\n        {\n            while(!pge.empty() && A[pge.top()] < A[i])\n                pge.pop();\n            if(!pge.empty()) left[i] = pge.top();\n            pge.push(i);\n            \n            while(!nge.empty() && A[nge.top()] < A[i]){\n                right[nge.top()] = i;\n                nge.pop();\n            }\n            nge.push(i);\n        }\n\n        for(int i=0;i<n;++i){\n            if(A[i] >=L && A[i]<=R){\n                ans+=(right[i]-i)*(i-left[i]);//Adds contribution of particular index into the ans value\n            }\n        }\n        return ans;          \n        }\n};\n        \n   \n```\nHope this helps!\nStay Safe!
['C', 'Monotonic Stack', 'C++']