Given an array of n integers, consider every one of its contiguous subarrays (including single-element subarrays and the whole array). For each subarray, its range span is its maximum element minus its minimum element (a single-element subarray has span 0). Sum the range span over all contiguous subarrays and print the total.
An efficient solution uses monotonic stacks to compute, for each element, how many subarrays it is the maximum of and how many it is the minimum of, then combines the two contributions.
Input format
Line 1: an integer n.
Line 2: n space-separated integers.
Output format
A single integer: the sum of the range span over every contiguous subarray.
Constraints
- 1 <= n <= 100000
- -1000000 <= each value <= 1000000