Problem Statement

You are given an array a of n positive integers. For every contiguous non-empty subarray of a , compute the product (maximum element of the subarray) x (number of elements in the subarray) Add up this product over all n * (n + 1) / 2 subarrays and print the total modulo 1000000007 . Input Format The first line contains a single integer n — the number of elements. The second line contains n space-separated integers a[0], a[1], ..., a[n-1] . Output Format Print a single integer — the sum of (subarray maximum) * (subarray length) over all contiguous non-empty subarrays, taken modulo 1000000007 . Constraints 1 <= n <= 100000 1 <= a[i] <= 1000000000 The exact (unreduced) total can be as large as about 10^23 , which does not fit in a signed 64-bit integer. Reduce modulo 1000000007 while accumulating. Every individual term of the standard counting argument stays below 10^18 and therefore fits in a signed 64-bit integer. Example 1 Input 3 1 2 3 Output 25 Explanation The six subarra