Đị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.

Ví dụ trọng số của dãy \((3,1,7,2)\) là \(6\), trọng số của dãy \((40,40)\) là \(0\).

Yêu cầu: Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\). Hãy tính tổng trọng số của tất cả các dãy con gồm các phần tử liên tiếp trong \(𝐴\).

Ví dụ với \(𝐴 = (1,2,3)\), những dãy con gồm các phần tử liên tiếp trong \(𝐴\) là:

• Dãy rỗng và các dãy (1), (2), (3): trọng số 0
• Dãy \((1,2)\) và dãy \((2,3)\): trọng số \(1\)
• Dãy \((1,2,3)\): trọng số \(2\)

=> Tổng trọng số cần tìm: \(4\)

Input

• Dòng 1 chứa số nguyên dương \(𝑛 \leq 4 \times 10^5\)
• Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) có giá trị không vượt quá \(10^6\).

Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm tìm được

Scoring

• Subtask \(1\) (\(32.5\%\) số điểm): \(𝑛 \leq 4 \times 10^2\)
• Subtask \(2\) (\(20\%\) số điểm): \(𝑛 \leq 10^4\)
• Subtask \(3\) (\(47.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\)

Example

3
1 2 3 

4

4
3 1 7 2 

31