Số cặp nghịch thế (Inversion Count) của một mảng \(A\) gồm N phần tử là số lượng cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j $\le N\) và \(A[i] > A[j]\).

Cho mảng \(A\) gồm các phần tử là một hoán vị của tập hợp \(\{1, 2, \dots, N\}\). Hãy tính số lượng cặp nghịch thế của mảng này.

Ví dụ

Input:

5
2 4 1 3 5

Output:

3

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N $\le 10^5\)).
• Dòng hai chứa \(N\) số nguyên phân biệt đại diện cho hoán vị.

Định dạng đầu ra

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