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~