Đề bài

Trong phần chơi thi đấu GARA STEM của ngày hội STEM cấp thành, phần thưởng cho đội thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số \(A\) cho trước.

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

Yêu cầu

Cho dãy số nguyên dương \(A = (a_1, a_2, \ldots, a_n)\). Hãy tìm tổng trọng số của tất cả các dãy con liên tiếp của \(A\).

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương \(n\) — số phần tử của dãy.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con liên tiếp của \(A\).

Ràng buộc

• \(1 \le n \le 10^6\)
• \(1 \le a_i \le 10^6\)

Ví dụ

Input 1

3  
1 2 3

Output 1

4

Giải thích

Các dãy con và trọng số:

• (1): 0
• (2): 0
• (3): 0
• (1,2): 1
• (2,3): 1
• (1,2,3): 2
  → Tổng = 4

Input 2

4  
3 1 7 2

Output 2

31