81828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
class Solution {
    /* Function to find the indices 
    of next smaller elements */
    findNSE(arr) {
        
        // Size of array
        const n = arr.length;
        
        // To store the answer
        const ans = new Array(n).fill(0);
        
        // Stack 
        const st = [];
        
        // Start traversing from the back
        for (let i = n - 1; i >= 0; i--) {
            
            // Get the current element
            const currEle = arr[i];
            
            // Pop the elements in the stack until 
            // the stack is not empty and the top 
            // element is not the smaller element
            while (st.length > 0 && arr[st[st.length - 1]] >= arr[i]) {
                st.pop();
            }
            
            // Update the answer
            ans[i] = st.length > 0 ? st[st.length - 1] : n;
            
            /* Push the index of current 
            element in the stack */
            st.push(i);
        }
        
        // Return the answer
        return ans;
    }
    
    /* Function to find the indices of 
    previous smaller or equal elements */
    findPSEE(arr) {
        
        // Size of array
        const n = arr.length;
        
        // To store the answer
        const ans = new Array(n).fill(0);
        
        // Stack 
        const st = [];
        
        // Traverse on the array
        for (let i = 0; i < n; i++) {
            
            // Get the current element
            const currEle = arr[i];
            
            // Pop the elements in the stack until 
            // the stack is not empty and the top 
            // elements are greater than the current element
            while (st.length > 0 && arr[st[st.length - 1]] > arr[i]) {
                st.pop();
            }
            
            // Update the answer
            ans[i] = st.length > 0 ? st[st.length - 1] : -1;
            
            /* Push the index of current 
            element in the stack */
            st.push(i);
        }
        
        // Return the answer
        return ans;
    }

    /* Function to find the sum of 
    the minimum value in each subarray */
    sumSubarrayMins(arr) {
        
        const nse = this.findNSE(arr);
        const psee = this.findPSEE(arr);
        
        // Size of array
        const n = arr.length;
        
        const mod = 1e9 + 7; // Mod value
        
        // To store the sum
        let sum = 0;
        
        // Traverse on the array
        for (let i = 0; i < n; i++) {
            
            // Count of first type of subarrays
            const left = i - psee[i];
            
            // Count of second type of subarrays
            const right = nse[i] - i;
            
            /* Count of subarrays where 
            current element is minimum */
            const freq = left * right * 1;
            
            // Contribution due to current element 
            const val = (freq * arr[i]) % mod;
            
            // Updating the sum
            sum = (sum + val) % mod;
        }
        
        // Return the computed sum
        return sum;
    }
}

// Main function to test the