Định nghĩa độ chênh lệch của dãy số ~A = \{a_1, a_2, \ldots, a_n\}~ bằng giá trị ~Max(A) - Min(A)~. Ví dụ: ~A = \{3, 1, 7, 2\}~ có giá trị là ~6~.

Bài toán cần giải quyết hôm nay là tính tổng độ chênh lệch của tất cả các dãy con (là các phần tử liên tiếp nhau của dãy) của một dãy ~A~ cho trước.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~1 \le n \le 3.10^5~.

~n~ dòng tiếp theo, mỗi dòng chứa một con số ~a_i~ là các phần tử của dãy số thỏa ~1 \le a_i \le 10^9~.

Output

In kết quả cần tìm.

Samples

Sample Input 1

3
1
2
3

Sample Output 1

4

Sample Input 2

4
3
1
7
2

Sample Output 2

31

REF: COCI