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\)