Sum of Subarray Minimums

Given an array of integers, the task is to calculate the sum of the minimum values of every contiguous subarray. For an array \(arr\) of length \(n\), consider every possible non-empty subarray. For each subarray, find the minimum element and then compute the sum over all such minimums. An efficient solution involves using a stack-based approach to determine, for each element, the span of subarrays in which it is the minimum.

Concepts involved: Arrays, Stacks, Subarrays, Dynamic Programming

inputFormat

The input is given via standard input. The first line contains an integer (n), representing the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Print a single integer to standard output, which is the sum of the minimum values of all subarrays.## sample

4
3 1 2 4

17