B. BITINVCNT – Đếm số nghịch thế

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

Đề bài

Cho dãy số nguyên dương gồm n phần tử a_1, a_2, …, a_n . Một cặp (a_i, a_j) được gọi là một nghịch thế nếu i < j a_i > a_j .

Cho biết số n và dãy số a_1, a_2, …, a_n , hãy đếm số nghịch thế trong dãy.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương n ;
  • Dòng thứ hai chứa n số nguyên a_1, a_2, …, a_n .

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

  • Một số nguyên duy nhất là số nghịch thế trong dãy.

Ví dụ:

Dữ liệu vào:
5
5 4 3 1 2
Dữ liệu ra:
9
Giải thích:
  • Các nghịch thế là (5, 4), (5, 3), (5, 1), (5, 2), (4, 3), (4, 1), (4, 2), (3, 1), (3, 2) .

Giới hạn:

  • 1 ≤ n ≤ 10^5; 1 ≤ a_i ≤ 10^6 .