Một văn phòng cần mã hóa \(N\) ký tự để tiết kiệm dung lượng lưu trữ. Ký tự thứ \(i\) xuất hiện \(f_i\) lần trong tài liệu. Để mã hóa, người ta gộp hai ký tự có tần suất nhỏ nhất lại với nhau, chi phí gộp bằng tổng tần suất của chúng. Quá trình lặp lại đến khi chỉ còn một nhóm duy nhất.

Hãy tính tổng chi phí nhỏ nhất để mã hóa toàn bộ tài liệu.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(f_1, f_2, ..., f_N\) (\(1 \le f_i \le 10^4\)).

Kết quả ra

• In ra tổng chi phí nhỏ nhất.

Ví dụ

Input

4
4 3 2 6

Output

29