Problem Statement

Sum of Subarray Strengths For a non-empty contiguous subarray, define its strength as its length multiplied by its maximum element. Find the sum of strengths of all contiguous subarrays, modulo `1000000007`. Input Format The first line contains `n`. The second line contains `n` positive integers. Output Format Print the required sum modulo `1000000007`. Constraints `1 <= n <= 100000` and `1 <= a[i] <= 1000000`. Notes If several equal values are maximum in a subarray, count that subarray once. Example Input: `3` then `1 2 3` produces `25`.