This was a candidate for problem 3 of the 2022 Spring Contest.

Nazuna wants to put on a Fireworks show for Zeyu to celebrate the end of exam season. To do this, she buys \(N\) firework launchers of varying types from stores across the country and lines them up in a row. Different types of fireworks have different fuzes, and will explode at different altitudes. More specifically, the \(i\)-th firework will explode at altitude \(h_i\). When Zeyu arrives after his last exam, he will select a random contiguous sequence of fireworks and launch them all at once.

As Nazuna is secretly in love with Zeyu, she wants to impress him. Before he arrives, she will tell him the sum of the ranges of all contiguous sequences of fireworks. The range of a contiguous sequence is the difference between the altitude of the highest and lowest firework explosion if all of the fireworks between some index \(L\) and \(R\) inclusive were launched at once, for some \(1 \le L \le R \le N\). However, Nazuna is tired after running all over the country to buy fireworks, so she asks you for help. As the sum could be very big, she asks you to give her the sum modulo \(1\,000\,000\,007\,(=10^9+7)\).

Input Specification

The first line contains the integer \(N\), the number of fireworks. The second line contains \(N\) space separated integers \(h_i\), representing the altitude at which the \(i\)-th firework will explode.

Output Specification

One integer, the sum of the ranges of all contiguous sequences of fireworks modulo \(1\,000\,000\,007\,(=10^9+7)\).

Input Constraints

Subtask 1 [20%]

\(1 \leq N \leq 2 \times 10^3\)

\(1 \leq h_i \leq 10^9\)

Subtask 2 [80%]

\(1 \leq N \leq 10^5\)

\(1 \leq h_i \leq 10^9\)

Sample Input 1

3
1 5 4

Sample Output 1

9

Explanation of Sample 1

The contiguous sequences of fireworks are as follows: \(\{1,5,4\}\), \(\{1,5\}\), \(\{5,4\}\), \(\{1\}\), \(\{5\}\), \(\{4\}\). The sum of their ranges is \((5-1)+(5-1)+(5-4)+(1-1)+(5-5)+(4-4) = 4+4+1+0+0+0 = 9\).

Sample Input 2

4
1 1000000000 1 1000000000

Sample Output 2

999999959

Explanation of Sample 2

Remember to print the answer modulo \(1\,000\,000\,007\).