Câu 4: Giá trị của dãy số (5.0 điểm)

Cho dãy \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\). Một đoạn con liên tiếp của dãy \(A\) là đoạn \(a_i, a_{i+1}, ..., a_r\) với \(1 \leq i < r \leq 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, ..., a_n\) có \(n\) phần tử, hãy tính giá trị của dãy số.

Input

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 \leq n \leq 10^5\));
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(|a_i| \leq 10^7\));

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

Output

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ố.

Example

3
2 4 1

8

Scoring

• Subtask 1 (1,5 điểm): \(1 \leq n \leq 100\).
• Subtask 2 (1,5 điểm): \(1 \leq n \leq 3000\).
• Subtask 3 (2,0 điểm): Không có ràng buộc gì thêm.