Cặp Nghịch Thế

Buổi 39 — DP + Data Structures
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho dãy số nguyên $A$ gồm $N$ phần tử. Một cặp chỉ số $(i, j)$ được gọi là một cặp nghịch thế nếu $1 \le i < j \le N$ và $A_i > A_j$. Hãy đếm tổng số cặp nghịch thế trong dãy $A$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $N$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.

Dữ liệu ra

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

Ví dụ
Input Output
5
5 4 3 2 1
10
6
2 4 1 3 5 2
6
Giới hạn
  • $1 \le N \le 2 \cdot 10^5$
  • $-10^9 \le A_i \le 10^9$
Draft saved