#5225. Đếm cặp nghịch thế (Mã bài: INVCNT)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy số nguyên A gồm n phần tử. Một cặp nghịch thế là một cặp chỉ số (i, j) thỏa mãn i < j A[i] > A[j] . Hãy đếm tổng số cặp nghịch thế trong dãy A .

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n ( 1 \le n \le 10^6 ) là số phần tử của dãy.
  • Dòng tiếp theo chứa n số nguyên A[i] ( 1 \le A[i] \le 10^7 ).

Kết quả: Ghin ra một dòng duy nhất chứa tổng số cặp nghịch thế.

Ví dụ:

Dữ liệu:

3
3 1 2

Kết quả:

2