Giá trị của dãy số

Cho dãy $A$ gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$. Một đoạn con liên tiếp của dãy $A$ là đoạn $a_l, a_{l+1}, \dots, a_r$ với $1 \le l \le r \le n$, giá trị đoạn con là độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của đoạn con. Giá trị của dãy số là tổng giá trị tất cả các đoạn con liên tiếp của dãy. Ví dụ: Cho dãy số 2 4 1 ta có các đoạn con liên tiếp $\{2\}, \{2, 4\}, \{2, 4, 1\}, \{4\}, \{4, 1\}, \{1\}$, giá trị dãy số là $0 + 3 + 0 + 3 + 0 + 2 = 8$.

Yêu cầu: Với dãy số nguyên dương $a_1, a_2, \dots, a_n$ có $n$ phần tử, hãy tính giá trị của dãy số.

Dữ liệu vào từ tệp văn bản CAU4.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^5$);
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^7$);

Các số trong tệp cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản CAU4.OUT một số nguyên duy nhất là giá trị của dãy số.