Thay thế tổng

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(n\) hộp kẹo trên bàn. Hộp thứ \(i\) chứa \(a_i\) viên kẹo. Bạn muốn gộp tất cả viên kẹo lại một hộp. Cách làm như sau:

Nếu trên bàn còn ít nhất hai hộp kẹo có kẹo, ta chọn ra hai hộp ít kẹo nhất rồi đổ chung vào một hộp. Nói cách khác, nếu hai hộp kẹo chứa \(x\)\(y\) viên kẹo, ta gộp chúng lại thành 1 hộp chứa \(x+y\) viên kẹo. Thời gian để thực hiện thao tác là \((x+y)\) giây.
Thực hiện đến khi nào trên bàn còn đúng một hộp kẹo.
In ra số lượng kẹo trong hộp sau khi thực hiện xong và tổng thời gian cần dùng.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n (1 \leq n \leq 2∗10^5)\), số hộp kẹo.
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\cdots,a_n (1 \leq a_i \leq 10^9)\)

Output

  • In ra hai số nguyên trên một dòng: số đầu tiên là số viên kẹo trong hộp cuối cùng, số thứ hai là tổng thời gian cần sử dụng.

Nếu bạn in đúng một trong hai số, bạn sẽ nhận được \(30\)% số điểm của test đó.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(30\%\) số điểm): \(n \leq 2000\)
  • Subtask \(3\) (\(50\%\) số điểm): \(n \leq 2∗ 10^5\).

Example

Test 1

Input
4
1 2 3 4 
Output
10 19
Note

Ban đầu, hai hộp kẹo ít nhất là \(1\)\(2\). Chúng ta gộp lại thành một hộp kẹo có \(3\) viên. Sau đó, có \(3\) hộp kẹo \([3,3,4]\), chọn ra hai hộp ít nhất là \(3\)\(3\) và gộp thành \(6\). Cuối cùng còn hai hộp \(4\)\(6\), gộp lại thành \(10\).
Tổng thời gian là \((1+2)+(3+3)+(6+4)=19\).


Bình luận