Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Sum of Subarray Minimums

Medium · Stack & Queue · Asked at Amazon, Google, Microsoft, Uber

For every contiguous subarray take its minimum; print the sum of all these minimums modulo 1,000,000,007.

Input

First line: n. Second line: n space-separated integers.

Output

The sum modulo 10^9 + 7.

Constraints

a[i] is the minimum of left[i] · right[i] subarrays, where left/right are distances to the previous smaller and next smaller-or-equal elements (monotonic stacks). Use strict on one side and non-strict on the other to avoid double counting equal values.

Example 1

Input

4
3 1 2 4

Output

17

Example 2

Input

5
11 81 94 43 3

Output

444

Hints

  1. Instead of looping over subarrays, ask: in how many subarrays is a[i] the minimum?
  2. left[i] = distance to the previous smaller element, right[i] = distance to the next smaller-or-equal element. a[i] is the minimum of left[i] · right[i] subarrays.

Approach

Two monotonic-stack passes compute left[i] (previous strictly smaller) and right[i] (next smaller or equal). Using strict on one side and non-strict on the other assigns a subarray with several equal minimums to exactly one of them. The answer is Σ a[i] · left[i] · right[i] mod 10^9+7 — use 64-bit products and reduce each term.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), left(n), right(n);
    for (auto &x : a) cin >> x;
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        left[i] = st.empty() ? i + 1 : i - st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        right[i] = st.empty() ? n - i : st.back() - i;
        st.push_back(i);
    }
    const long long MOD = 1000000007LL;
    long long ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + a[i] % MOD * left[i] % MOD * right[i]) % MOD;
    cout << ans << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
left, right, st = [0] * n, [0] * n, []
for i in range(n):
    while st and a[st[-1]] >= a[i]:
        st.pop()
    left[i] = i - st[-1] if st else i + 1
    st.append(i)
st = []
for i in range(n - 1, -1, -1):
    while st and a[st[-1]] > a[i]:
        st.pop()
    right[i] = st[-1] - i if st else n - i
    st.append(i)
print(sum(a[i] * left[i] * right[i] for i in range(n)) % (10**9 + 7))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n], left = new long[n], right = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int[] st = new int[n];
        int top = 0;
        for (int i = 0; i < n; i++) {
            while (top > 0 && a[st[top - 1]] >= a[i]) top--;
            left[i] = top == 0 ? i + 1 : i - st[top - 1];
            st[top++] = i;
        }
        top = 0;
        for (int i = n - 1; i >= 0; i--) {
            while (top > 0 && a[st[top - 1]] > a[i]) top--;
            right[i] = top == 0 ? n - i : st[top - 1] - i;
            st[top++] = i;
        }
        long MOD = 1000000007L, ans = 0;
        for (int i = 0; i < n; i++) ans = (ans + a[i] % MOD * left[i] % MOD * right[i]) % MOD;
        System.out.println(ans);
    }
}

Solve Sum of Subarray Minimums online · All practice problems