Min-Max-Multiply!#485

Min-Max-Multiply!

1 second
256 megabytes
Very hard

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

\operatorname{mn}(l,r) = \min(a_l, a_{l+1}, \dots, a_r),
\operatorname{mx}(l, r) = \max(a_l, a_{l+1}, \dots, a_r).

Now he is interested in the value

S = \sum_{l=1}^{n} \sum_{r=l}^{n} \operatorname{mn}(l, r) \cdot \operatorname{mx}(l, r).

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!

Input

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).

Output

Print a single integer — the value of the remainder of modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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.

Scoring

In each block, the tests are evaluated independently.

  1. ( points): n \leq 2000;

  2. ( points): a_i \leq a_{i+1} for all 1 \leq i \leq n-1;

  3. ( points): among the elements of there are at most distinct values;

  4. ( points): n \leq 10^5;

  5. ( points): no additional restrictions.