Có \(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\) và \(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

4
1 2 3 4 

10 19