Sum of Subarray Minimums in java

Given an array of integers arr, find the sum of the minimums of all contiguous subarrays of the array. Since the answer may be large, print the answer modulo 10^9 + 7.

Input Format

The first line contains a single integer n(size of the array) The second line contains n space integers that denote the elements of the array

Output Format

Print the sum of minimum of all subarrays

Example 1

Input

4
3 1 2 4

Output

17

Explanation

Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.

Example 2

Input

5
11 81 94 43 3

Output

444

Constraints

1 <= arr.length <= 3 * 10^4 1 <= arr[i] <= 3 * 10^4

Solution:–

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) {
 
      Scanner sc= new Scanner(System.in);
      int n= sc.nextInt();
      int[] arr= new int[n];
 
      for(int i=0; i<n; i++) {
        arr[i]= sc.nextInt();
      }
 
      int[] left= new int[n];
      int[] right= new int[n];
 
      Stack<Integer> st= new Stack<>();
 
      for(int i=0; i<n; i++) {
        while(!st.empty() && arr[st.peek()] >= arr[i]){
 
          st.pop();
        }
 
        if(st.empty()) {
          left[i]= i ;
          st.push(i);
        }
        else{
          left[i]= i- st.peek()-1;
          st.push(i);
        }
      }
 
      Stack<Integer> sk= new Stack<>();
 
      for(int i=n-1; i>=0; i--) {
 
        while(!sk.empty() && arr[sk.peek()] >arr[i]){   // case ''>''
          sk.pop();
        }
 
        if(sk.empty()) {
          right[i]= n-i-1;
          sk.push(i);
        }
        else {
          right[i]= sk.peek()-i-1;
          sk.push(i);
        }
      }
 
      long ans=0;
      int mod= 1000000007;
      
      for(int i=0; i<n; i++){
 
        ans += (arr[i]*(left[i]+1)*(right[i]+1)) % mod;
        ans= ans%mod;
 
      }
      System.out.println(ans);
    }
}