One beautiful morning, J97 sat by the window, holding a cup of hot coffee, watching the clouds drifting by. Today was a day off, and J97 wanted to take some time to reflect on what he had experienced. Like many people, J97's life was a series of ordinary days interspersed with a few special moments, sometimes filled with joy, sometimes tinged with a bit of sadness. And, like everyone else, J97 realized that his life had "weights" - moments when the ups and downs were more pronounced, leaving a deeper mark in his heart.

J97 suddenly thought: "If every day, every sequence of memories, were a number, then what would be the 'weight' of that sequence of memories?" He imagined that for each memory segment - from the shortest, consisting of just one moment, to the longest, including the entire past year - he could measure the "weight" of that segment: the difference between the best and worst moments of each memory. A very peaceful day would have a weight of 0, while a week with all kinds of emotions would have a greater weight.

With this thought, J97 decided to find a way to calculate the sum of all the "weights" of the memory segments in his life, from the shortest to the longest. This was an interesting problem, and he found a way to simulate it with an integer array ~A~, which contains ~n~ elements: ~A_1, A_2, ..., A_n~. Now, J97 wants you to help him calculate the total weight of all contiguous subarrays of ~A~ to understand the weight of his life. The weight of a subarray is defined as the difference between the maximum and minimum elements in that subarray.

Input:

• The first line contains a positive integer ~n~ (~n \leq 4 \times 10^5~).
• The second line contains ~n~ positive integers ~A_1, A_2, ..., A_n~ (~A_i \leq 10^6~).

Output:

• A single integer representing the result.

Sample Input

3 
1 2 3

Sample Output

4

Notes

The weights are represented as follows:

• ~[1, 2] = (2 - 1) = 1~
• ~[1, 3] = (3 - 1) = 2~
• ~[2, 3] = (3 - 2) = 1~

Constraints:

• Subtask ~1~ (~30\%~ of points): ~n \leq 4 \times 10^2~
• Subtask ~2~ (~30\%~ of points): ~n \leq 10^4~
• Subtask ~3~ (~40\%~ of points): No additional constraints.