Mister IP found an integer array of length . He is free on the weekend, so he found himself an occupation:
For each subarray (1 \le l \le r \le n), define
Now he is interested in the value
Since it may be very large, he only wants to know its remainder when divided by 10^9 + 7 (in other words, S \mod (10^9 + 7)). Help him calculate it!
The first line contains a single integer (1 \le n \le 5 \cdot 10^5) — the length of the array.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^6).
Print a single integer — the value of the remainder of modulo 10^9 + 7.
Example 1
Example 2
In the first example, all subarrays and their contributions are:
: \min = 1, \max = 1, contribution 1 \cdot 1 = 1
: \min = 1, \max = 2, contribution 1 \cdot 2 = 2
[1,2,3]: \min = 1, \max = 3, contribution 1 \cdot 3 = 3
: \min = 2, \max = 2, contribution 2 \cdot 2 = 4
: \min = 2, \max = 3, contribution 2 \cdot 3 = 6
: \min = 3, \max = 3, contribution 3 \cdot 3 = 9
The sum of all contributions is 1 + 2 + 3 + 4 + 6 + 9 = 25.
In each block, the tests are evaluated independently.
( points): n \leq 2000;
( points): a_i \leq a_{i+1} for all 1 \leq i \leq n-1;
( points): among the elements of there are at most distinct values;
( points): n \leq 10^5;
( points): no additional restrictions.