Cho dãy \(A\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\). Một đoạn con liên tiếp của dãy \(A\) là đoạn \(a_l, a_{l+1}, ..., 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.

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

Input

• 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, ..., a_n\) (\(|a_i| \le 10^7\)). Các số cách nhau bởi dấu cách.

Output

• In ra 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 \le n \le 100\).
• Subtask \(2\) (\(1{,}5\) điểm): \(1 \le n \le 3000\).
• Subtask \(3\) (\(2{,}0\) điểm): Không ràng buộc gì thêm.