Đếm cặp đảo thứ tự

Bối cảnh và bài toán

Một chuỗi bản ghi đáng lẽ tăng theo thứ tự ưu tiên. Một cặp (i,j) với i<j nhưng a[i]>a[j] biểu thị một lần đảo thứ tự. Với dữ liệu lớn, kiểm mọi cặp là quá chậm.

Yêu cầu

Đếm tổng số cặp đảo thứ tự.

Input

• Dòng 1: n.
• Dòng 2: n số nguyên a[i].

Output

In số inversion.

Ràng buộc

• 1 <= n <= 2 * 10^5
• |a[i]| <= 10^9

Chấm điểm

Ví dụ 1

Input

3
3 1 2

Output

2

Giải thích. Các inversion là (3,1) và (3,2).

Ví dụ 2

Input

5
5 4 3 2 1

Output

10

Giải thích. Mọi cặp i<j đều là inversion, tổng C(5,2)=10.

Thông tin bài tập

Nguồn: Phỏng theo SPOJ — INVCNT (Code Wars 2010).

Tham khảo: https://www.spoj.com/problems/INVCNT/