Vương quốc LQDOJ đang tổ chức một cuộc tuyển chọn gắt gao để tìm ra một "Thành viên ưu tú" duy nhất. Có \(n\) ứng cử viên tham gia, mỗi người sở hữu một chỉ số sức mạnh riêng biệt là \(a_i\).

Để tìm ra người xứng đáng nhất, ban tổ chức thực hiện các cuộc đối đầu sinh tử. Trong mỗi cuộc đối đầu, họ sẽ chọn ra hai người bất kỳ từ danh sách hiện tại. Quy tắc của cuộc đấu rất khắc nghiệt: người có sức mạnh lớn hơn sẽ bị loại khỏi cuộc thi ngay lập tức. Chi phí để tổ chức một trận đấu như vậy được tính bằng đúng chỉ số sức mạnh của người chiến thắng (người có sức mạnh nhỏ hơn trong cặp đấu đó).

Quá trình này sẽ lặp đi lặp lại cho đến khi chỉ còn đúng một người duy nhất trụ lại trong danh sách. Là một cố vấn chiến lược của vương quốc, bạn hãy tính toán tổng chi phí tối thiểu để ban tổ chức có thể tìm ra "Thành viên ưu tú" cuối cùng.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)) là số lượng ứng cử viên.
• Dòng thứ hai chứa \(n\) số nguyên phân biệt \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) lần lượt là chỉ số sức mạnh của từng người.

Output

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu để rút gọn danh sách xuống còn một người.

Example

3
4 3 2

4

2
3 4

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \le 10^5\) và \(a_i \le 10^9\).