Maged has dropped out of his computer science degree after seeing the slumps in the job market, and is now hoping to make it big as a crypto day trader. He is hoping to analyse past trends in his favorite cryptocurrency, XRP, in order to make it big in the future.

Maged has recorded the price of XRP at regular intervals into an array called ~A~. He is interested in a measure he calls "volatility", where volatility over a given time interval (subarray ~A[i ... j]~) is given by the highest price in that interval, minus the lowest price — in other words, ~\text{volatility} = \max(A[i ... j])-\min(A[i ... j])~.

He hopes to understand the market more by summing all the volatility values over all consecutive subarrays in his dataset ~A~, as every price change is a missed opportunity for profit.

Input

The first line contains a single integer ~n~ ~(1 \leq n \leq 3\times10^5)~, the number of data points in Maged's dataset ~A~.

The next line contains ~n~ space-separated integers ~a_i~ ~(1 \leq a_i \leq 10^8)~, representing the values in the dataset ~A~.

Output

The "volatility" value of an array is determined by its maximum value subtracted by its minimum value. Output the sum of the volatility values of all consecutive subarrays of ~A~.

Example

Input 1

5
1 10 3 8 9

Output 1

69

We can enumerate all possible subarrays and their values as follows. Note that 1-element subarrays will always contribute ~0~.

• 1 10: ~10-1 = 9~
• 1 10 3: ~10-1 = 9~
• 1 10 3 8: ~10-1 = 9~
• 1 10 3 8 9: ~10-1 = 9~
• 10 3: ~10-3 = 7~
• 10 3 8: ~10-3 = 7~
• 10 3 8 9: ~10-3 = 7~
• 3 8: ~8-3=5~
• 3 8 9: ~9-3=6~
• 8 9: ~9-8=1~

~9+9+9+9+7+7+7+5+6+1=69~

Input 2

8
1 2 3 4 10 9 8 7

Output 2

140