Hàng Ưu Tiên Khư Phát Tân Phú

Mô tả

Sáng sớm tại UBND quận Tân Phú, bà con xếp hàng dài để nhận gói hỗ trợ. Quy định rất rõ: người có mã ưu tiên càng nhỏ thì càng được gọi lên trước. Trong thực tế, cán bộ ghi nhận danh sách theo đúng thứ tự mọi người đến và lấy số. Khi nhìn bảng thứ tự, nhiều người phát hiện ra có những người đến sau nhưng mã ưu tiên lại nhỏ hơn, đáng lẽ phải được phục vụ trước.

Bài toán đặt ra: cho danh sách mã ưu tiên của ( n ) người theo đúng thứ tự xếp hàng, hãy đếm xem có tất cả bao nhiêu cặp ((i, j)) sao cho người thứ (i) đến trước người thứ (j) (tức là ( i < j )) nhưng mã ưu tiên của người thứ (i) lại lớn hơn người thứ (j) (tức là ( a_i > a_j )). Đây chính là số lượng "cặp nghịch thế" trong dãy mã ưu tiên.

Đầu vào

• Dòng đầu chứa một số nguyên dương ( n ) — số người trong hàng.
• Dòng thứ hai chứa ( n ) số nguyên ( a_1, a_2, ..., a_n ) — mã ưu tiên của từng người theo thứ tự xếp hàng.

Đầu ra

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

Ràng buộc

• ( 1 \le n \le 10^5 )
• ( 1 \le a_i \le 10^9 )
• Kết quả tối đa đạt ( n \times (n-1) / 2 ), có thể vượt ( 2^{31} ), nên cần dùng kiểu số nguyên 64-bit.

Ví dụ

Ví dụ 1:

• Đầu vào:

5 5 3 2 4 1

• Đầu ra:

8

Giải thích từng bước:

• Người 1 (mã 5): lớn hơn 3, 2, 4, 1 → 4 cặp.
• Người 2 (mã 3): lớn hơn 2, 1 → 2 cặp.
• Người 3 (mã 2): lớn hơn 1 → 1 cặp.
• Người 4 (mã 4): lớn hơn 1 → 1 cặp.
• Người 5 (mã 1): không lớn hơn ai → 0 cặp.
• Tổng cộng: ( 4 + 2 + 1 + 1 = 8 ) cặp nghịch thế.