Trong kỳ thi Olympic Tin học tỉnh BG, phần thưởng cho người thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số $a$ cho trước.

Định nghĩa trọng số của một 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.

Yêu cầu: Cho dãy số nguyên dương $a = (a_1, a_2,..,a_n)$. Hãy tìm phần thưởng dành cho người thắng cuộc.

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à dãy có 1 phần tử (1), (2), (3) đều có trọng số bằng 0.
• Dãy (1, 2) và dãy (2, 3) đều có trọng số bằng 1;
• Dãy (1, 2, 3) có trọng số bằng 2.

Phần thưởng cho người thắng cuộc là 0 + 1 + 1 + 2 = 4

Dữ liệu vào:

• Dòng 1: Chứa một số nguyên dương $n (n \le 10^6)$.
• Dòng 2: Ghi $n$ số nguyên dương $a_1, a_2,..., a_n$ có giá trị không quá $10^6$ ;

Dữ liệu ra:

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

Ví dụ:

Giới hạn:

• Subtask 1: Có 10/30 test ứng với 1 điểm $n \le 10^3$
• Subtask 2: có 20/30 test ứng với 2 điểm $10^3 < n \le 10^6$