Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy. Ví dụ trọng số của dãy (3,1,7,2) là 6, trọng số của dãy (40,40) là 0.

Yêu cầu

Cho dãy số nguyên \(A=~(a_1,a_2,…,a_n)~\). Hãy tính tổng trọng số của tất cả các dãy con gồm các phần tử liên tiếp trong ~A~.
Ví dụ: với ~A~= (1,2,3), những dãy con gồm các phần tử liên tiếp trong ~A~ là:

• Dãy rỗng và các dãy (1,2,3): trọng số 0
• Dãy (1,2) và dãy (2,3): trọng số 1
• Dãy (1,2,3): trọng số 2
  Tổng trọng số cần tìm: 4

Dữ liệu

Dòng 1: Chứa số nguyên dương ~n~.
Dòng 2: Chứa ~n~ số nguyên ~a_1,a_2,…,a_n~.

Kết quả

Một số nguyên duy nhất là kết quả tìm được.

Giới hạn

\(n \leq ~10^6~, ∀i:|~a_i~| \leq ~10^6~\).

Input 1

3
1 2 3

Output

4

Input 2

4 
3 1 7 2

Output

31