Appleman và Toastman

Cho một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$. Ban đầu dãy này được xem như một nhóm duy nhất. Trò chơi diễn ra như sau:

• Mỗi khi nhận được một nhóm, ta cộng tổng các phần tử của nhóm vào tổng điểm chung.
• Nếu nhóm vừa nhận có nhiều hơn $1$ phần tử, ta chia nó thành hai nhóm con khác rỗng (cách chia tuỳ ý) và xử lý tiếp từng nhóm con. Nếu nhóm chỉ có đúng $1$ phần tử thì loại bỏ.

Hãy xác định giá trị lớn nhất của tổng điểm có thể đạt được sau khi mọi nhóm đều bị loại bỏ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Một số nguyên duy nhất — tổng điểm lớn nhất có thể đạt được.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $1\le a_i\le {10}^6$

Ví dụ