**Sum of Subarray Ranges (Leetcode 2104)

Problem Link: https://leetcode.com/problems/sum-of-subarray-ranges/

TC: O(N) and SC: O(N)

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        
        # Traverse through the array and calculate the
        # number of times the curr element is minimum 
        # and number of times it is the maximum.
        
        n=len(nums)
        nsl=[]
        nsr=[]
        ngl=[]
        ngr=[]
        
        s=[]
        for i in range(n):
            if(len(s)==0):
                nsl.append(-1)
            else:
                # Slight variation in below line
                if(nums[s[-1]]<=nums[i]):
                    nsl.append(s[-1])
                else:
                    # Slight variation in below line
                    while(len(s)>0 and nums[s[-1]]>nums[i]):
                        s.pop()
                    if(len(s)==0):
                        nsl.append(-1)
                    else:
                        nsl.append(s[-1])
            s.append(i)
            
        s=[]
        for i in range(n):
            if(len(s)==0):
                ngl.append(-1)
            else:
                # Slight variation in below line
                if(nums[s[-1]]>=nums[i]):
                    ngl.append(s[-1])
                else:
                    # Slight variation in below line
                    while(len(s)>0 and nums[s[-1]]<nums[i]):
                        s.pop()
                    if(len(s)==0):
                        ngl.append(-1)
                    else:
                        ngl.append(s[-1])
            s.append(i)
            
        s=[]
        for i in range(n-1,-1,-1):
            if(len(s)==0):
                nsr.append(n)
            else:
                if(nums[s[-1]]<nums[i]):
                    nsr.append(s[-1])
                else:
                    while(len(s)>0 and nums[s[-1]]>=nums[i]):
                        s.pop()
                    if(len(s)==0):
                        nsr.append(n)
                    else:
                        nsr.append(s[-1])
            s.append(i)
        
        nsr=nsr[::-1]
        
        s=[]
        for i in range(n-1,-1,-1):
            if(len(s)==0):
                ngr.append(n)
            else:
                if(nums[s[-1]]>nums[i]):
                    ngr.append(s[-1])
                else:
                    while(len(s)>0 and nums[s[-1]]<=nums[i]):
                        s.pop()
                    if(len(s)==0):
                        ngr.append(n)
                    else:
                        ngr.append(s[-1])
            s.append(i)
        
        ngr=ngr[::-1]
        
        # print(nsl)
        # print(nsr)
        # print(ngl)
        # print(ngr)
        ans=0
        for i in range(n):
            lessertoleft=i-nsl[i]-1
            lessertoright=nsr[i]-i-1
            greatertoleft=i-ngl[i]-1
            greatertoright=ngr[i]-i-1
            ans=ans+(greatertoleft+1)*(greatertoright+1)*nums[i]
            ans=ans-(lessertoleft+1)*(lessertoright+1)*nums[i]
        
        return ans