Độ lệch thứ tự (Order Deviation)

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

Đề bài

Cho dãy $A_1,A_2,\ldots,A_N$. Với mỗi cặp chỉ số $(i,j)$ thỏa $1\le i<j\le N$ và $A_i>A_j$, cặp này đóng góp một lượng bằng $A_i-A_j$.

Hãy tính

$$T=\sum_{\substack{1\le i<j\le N\\ A_i>A_j}}(A_i-A_j).$$

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 một số nguyên duy nhất là $T$.

Subtask

• Subtask 1 — 40%: $1\le N\le 2000$, $0\le A_i\le 10^6$.
• Subtask 2 — 20%: $1\le N\le 2\cdot 10^5$; dãy $A$ là một hoán vị của $1,2,\ldots,N$.
• Subtask 3 — 40%: $1\le N\le 2\cdot 10^5$, $0\le A_i\le 10^6$.

Ví dụ

Ví dụ 1

Input

4
5 1 4 2

Output

10

Giải thích

Các đóng góp là $4,1,3,2$ tương ứng với các cặp $(1,2),(1,3),(1,4),(3,4)$. Tổng bằng $10$.

Ví dụ 2

Input

5
1 2 3 4 5

Output

0

Giải thích

Không tồn tại cặp $i<j$ với $A_i>A_j$.