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

Dữ liệu vào:

• Dòng 1 chứa số nguyên dương 𝑛 ≤ 4.~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.

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

Ví dụ:

INPUT 1

3
1 2 3

OUTPUT 1

4

INPUT 2

4
3 1 7 2

OUTPUT 2

31