Given an array A of integers. Find the sum of min(ai,ai+1,...,aj) for every pair (i,j), where 1≤i≤j≤n.
The first line contains the size n (1≤n≤105) of array A. The second line contains n integers ai (1≤ai≤105) — the elements of array.
Print the the sum of min(ai,ai+1,...,aj) modulo 109+7.
Consider the first test case.
Subarrays are {3},{1},{2},{4},{3,1},{1,2},{2,4},{3,1,2},{1,2,4},{3,1,2,4}.
Minimums are 3,1,2,4,1,1,2,1,1,1. Their sum is 17.