#5196. WAITTIME - Thời gian chờ đợi

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

Tại một ngân hàng, có N khách hàng đang xếp hàng chờ được phục vụ. Người thứ i cần t_i phút để hoàn thành giao dịch của mình. Tổng thời gian chờ của một khách hàng được tính bằng tổng thời gian phục vụ của tất cả những người đứng trước họ trong hàng. Ngân hàng muốn sắp xếp lại thứ tự của các khách hàng để tổng thời gian chờ của tất cả N người là nhỏ nhất có thể.

Hãy tính tổng thời gian chờ nhỏ nhất đó.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n\ (1 \le n \le 10^5) .
  • Dòng thứ hai chứa n số nguyên t_1, t_2, ..., t_n\ (1 \le t_i \le 10^9) .

Kết quả: Một số nguyên duy nhất là tổng thời gian chờ nhỏ nhất có thể.

Ví dụ:

Dữ liệu:

5
3 1 4 1 5

Kết quả:

17

Dữ liệu:

3
5 1 2

Kết quả:

4

Giới hạn:

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