Xây đường

Khu phố có tổng cộng ~n~ địa điểm, ban đầu chưa có đường nối. Mỗi địa điểm ~i~ ~(1 \le i \le n)~ có một trọng số ~w_i~. Chi phí để xây đường nối hai chiều giữa hai địa điểm ~u~ và ~v~ là ~w_u + w_v~.

Hãy xác định tổng chi phí nhỏ nhất để xây dựng các đường nối sao cho xuất phát từ bất kỳ địa điểm nào đều có thể đến được mọi địa điểm còn lại.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~w_i~ ~(1 \le w_i \le 10^9)~.

Output

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

Samples

1
10

0

3
5 5 5

20

4
7 3 3 5

24

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~w_1=w_2=...=w_n~
• Subtask ~2~ với ~30\%~ số điểm: ~n \le 1000~
• Subtask ~3~ với ~40\%~ số điểm: Không còn ràng buộc gì thêm