Tổng dao động (Sum of Range Oscillations)

Phiên bản: Phước Hưng OJ

Đề bài

Cho dãy $N$ số nguyên $A_1,A_2,\ldots,A_N$. Với $1\le L\le R\le N$, đoạn liên tiếp $[L,R]$ gồm các phần tử $A_L,A_{L+1},\ldots,A_R$. Độ dao động của đoạn được định nghĩa bởi

$$D(L,R)=\max_{L\le i\le R}A_i-\min_{L\le i\le R}A_i.$$

Hãy tính tổng độ dao động của tất cả các đoạn liên tiếp không rỗng:

$$\mathrm{Ans}=\sum_{1\le L\le R\le N}D(L,R).$$

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra một số nguyên duy nhất là $\mathrm{Ans}$.

Subtask

• Subtask 1 (37.5%): $1\le N\le 500$, $|A_i|\le 10^6$.
• Subtask 2 (25%): $1\le N\le 5000$, $|A_i|\le 10^6$.
• Subtask 3 (37.5%): $1\le N\le 2\times10^5$, $|A_i|\le 10^6$.

Ví dụ

Ví dụ 1

Input

3
1 3 2

Output

5

Giải thích

Các đoạn có độ dao động khác $0$ là $[1,2]$ có độ dao động $2$, $[2,3]$ có độ dao động $1$ và $[1,3]$ có độ dao động $2$. Tổng bằng $5$.

Ví dụ 2

Input

4
7 7 7 7

Output

0

Giải thích

Mọi đoạn đều có giá trị lớn nhất bằng giá trị nhỏ nhất nên độ dao động bằng $0$.