**Sum of Subarray Minimums (Leetcode 907)

Learn NSL and NSR for this

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

class Solution:
    def sumSubarrayMins(self, nums: List[int]) -> int:
        
        nsl=[]
        nsr=[]
        n=len(nums)
        s=[]
        
        # Find the Nearest smaller to left and 
        # Nearest smaller to right.
        
        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-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]
        print(nsl)
        print(nsr)
        ans=0
        for i in range(n):
            # Now calculate the number of larger elements to left
            # and number of larger elements to right for each element.
            
            leftele=i-nsl[i]-1
            rightele=nsr[i]-i-1
            # print(leftele,rightele)
            ans=ans+nums[i]*(leftele+1)*(rightele+1)
        return ans%1000000007