Tí có một mảng gồm \(N\) số nguyên và muốn đếm số lượng cặp nghịch thế trong mảng đó. Cặp nghịch thế là một cặp chỉ số \((i, j)\) sao cho: \(1 \le i < j \le N\) và \(A_i > A_j\)

Hãy giúp Tí lập trình giải quyết bài toán này với độ phức tạp tối ưu hơn thuật toán duyệt trâu \(O(N^2)\).

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) cách nhau bởi dấu cách (\(-10^9 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là số lượng cặp nghịch thế tìm được.

Ví dụ

Đầu vào:

5
2 3 8 6 1

Đầu ra:

5

Giải thích: Các cặp nghịch thế là: \((2, 1)\) vì 2 > 1; \((3, 1)\) vì 3 > 1; \((8, 6)\) vì 8 > 6; \((8, 1)\) vì 8 > 1; \((6, 1)\) vì 6 > 1.