Trong cuộc thi Olympic Tin học của 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 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.

Yêu cầu: Cho dãy số nguyên dương \(a\ = \ (a_{1},\ a_{2},\ \ldots\ ,\ a_{n})\). Hãy tìm phần thưởng 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à các dãy có 1 phần tử (1), (2), (3) đều có trọng số 0;

- Dãy (1, 2) và dãy (2, 3) đều có trọng số 1;

- Dãy (1, 2, 3) có trọng số 2.

Phần thưởng cho người thắng cuộc bằng \(0 + 1 + 1 + 2 = 4\).

Dữ liệu vào:

- Dòng 1 chứa số nguyên dương \(n\ (n < 10^{6})\);

- Dòng 2 chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) có giá trị không vượt quá \(10^{6}\).

Kết quả:

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

Ví dụ:

Giới hạn:

- Có 10/30 test, tương ứng với 1 điểm có \(n < 10^{3}\);

- Có 20/30 test, tương ứng với 2 điểm có \(n < 10^{6}\).