Đếm nghịch thế bằng chỉ số tần suất

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

Một dãy số phân biệt cần được đánh giá mức độ "lộn xộn". Mỗi cặp chỉ số i < j nhưng a[i] > a[j] được tính là một nghịch thế. Ở B12 ta đã biết một lời giải dựa trên merge; lần này mục tiêu là khai thác kiến thức cấu trúc truy vấn tần suất để nhìn lại cùng bài toán từ một góc khác.

Yêu cầu

Tính tổng số nghịch thế của dãy.

Input

• Dòng 1 chứa n.
• Dòng 2 chứa n số nguyên phân biệt.

Output

In số nghịch thế của dãy.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a[i] <= 10^9
• Các giá trị đôi một khác nhau.

Chấm điểm

Ví dụ 1

Input

5
2 3 8 6 1

Output

5

Giải thích. Các nghịch thế là (2,1), (3,1), (8,6), (8,1), (6,1).

Ví dụ 2

Input

4
4 3 2 1

Output

6

Giải thích. Dãy giảm hoàn toàn có n(n-1)/2 = 6 nghịch thế.

Thông tin bài tập

Nguồn: Phỏng theo SPOJ INVCNT – Inversion Count.