Sum of Subarray Minimums

Input

The first line contains the size $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) of array $A$ . The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ a_i~(1 \le a_i \le 10^5) — the elements of array.

Output

Print the sum of $min (a_{i}, a_{i + 1}, ..., a_{j})$ \min(a_i, a_{i+1}, ..., a_j) modulo $1 0^{9} + 7$ 10^9 + 7.

Examples

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}$ \{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$ 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Their sum is $17$ .

Example 1

Loading

Example 2

Loading