Đếm nghịch thế

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\). Một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) và \(a_i > a_j\). Hãy đếm số cặp nghịch thế của dãy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Một số nguyên là số cặp nghịch thế.

Subtask

• \(40\%\) số test: \(n \le 2000\).
• \(60\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

5
3 1 4 1 2

Sample Output 1

5

Notes

Các cặp nghịch thế (theo giá trị) là \((3,1)\), \((3,1)\), \((3,2)\), \((4,1)\), \((4,2)\).