907. Sum of Subarray Minimums

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        Stack<Integer> sk = new Stack<>();
        long left [] = new long [n];
        for(int i = 0; i < n; i ++){
            while(!sk.isEmpty() && arr[i] < arr[sk.peek()]){
                sk.pop();
            }
            left[i] = sk.isEmpty() ? 0 : sk.peek() + 1;
            sk.push(i);
        }
        sk.clear();
        long right [] = new long [n];
        for(int i = n - 1; i >= 0; i --){
            while(!sk.isEmpty() && arr[i] <= arr[sk.peek()]){
                sk.pop();
            }
            right[i] = sk.isEmpty() ? n - 1 : sk.peek() - 1;
            sk.push(i);
        }
        
        long ans = 0;
        for(int i = 0; i < n; i++){
            ans = (ans + (long)(i - left[i] + 1)* (long)(right[i] - i + 1)*arr[i]) % 1000_000_007;
        }
        return (int)ans;
    }
}