#5216. WEIGHTINV - Số cặp nghịch thế có trọng số

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 mảng a gồm n số nguyên. Một cặp chỉ số (i, j) được gọi là một cặp nghịch thế nếu i < j a_i > a_j . Hãy tính tổng của a_i + a_j trên tất cả các cặp nghịch thế.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n ( 1 \le n \le 10^5 ) - kích thước của mảng.
  • Dòng thứ hai chứa n số nguyên a_i ( 1 \le a_i \le 10^9 ).

Kết quả: In ra một số nguyên duy nhất là tổng của a_i + a_j trên tất cả các cặp nghịch thế.

Ví dụ:

Dữ liệu:

5
5 3 6 1 4

Kết quả:

44

Giới hạn:

  • 1 \le n \le 10^5
  • 1 \le a_i \le 10^9