Đếm Cặp Tăng Trưởng Du Lịch Thăng Long

Mô tả

Website du lịch Thăng Long ghi lại lượt truy cập hàng ngày trong một mùa cao điểm. Ban phân tích dữ liệu muốn biết có bao nhiêu cặp ngày (p, q) mà ngày đứng trước có lượt truy cập nhỏ hơn nghiêm ngặt so với ngày đứng sau, tức là p < q và a[p] < a[q]. Mỗi cặp như vậy đại diện cho một "tín hiệu tăng trưởng" giữa hai thời điểm.

Vì dữ liệu rất lớn, kiểm tra từng cặp bằng hai vòng lặp sẽ quá chậm. Bạn cần thiết kế thuật toán hiệu quả hơn để đếm chính xác tổng số cặp thỏa mãn.

Đầu vào

• Dòng đầu tiên chứa số nguyên n (số ngày ghi nhận).
• Dòng thứ hai chứa n số nguyên a[0], a[1], ..., a[n-1], mỗi số là lượt truy cập của một ngày.

Đầu ra

• In ra một số nguyên duy nhất là tổng số cặp (p, q) với 0 <= p < q <= n-1 sao cho a[p] < a[q].

Ràng buộc

• 1 <= n <= 100,000
• 0 <= a[i] <= 1,000,000,000
• Kết quả có thể lên tới ~5 * 10^9, cần chú ý kiểu dữ liệu 64-bit.

Ví dụ

Ví dụ 1

Đầu vào:

5 3 1 4 1 5

Đầu ra:

6

Giải thích: Các cặp (p, q) thỏa mãn a[p] < a[q] là: (0,2) vì 3<4, (0,4) vì 3<5, (1,2) vì 1<4, (1,3) vì 1=1 không tính, (1,4) vì 1<5, (2,4) vì 4<5, (3,4) vì 1<5. Tổng cộng có 6 cặp tăng trưởng.