Autići

Υπάρχουν n φίλοι. Κάθε φίλος έχει ένα τηλεκατευθυνόμενο αυτοκίνητο-παιχνίδι και ένα γκαράζ στο οποίο είναι αποθηκευμένο το αυτοκίνητο. Κάθε φίλος έχει επίσης ένα πακέτο εξαρτημάτων δρόμου που χρησιμοποιείται για να φτιαχτεί η πίστα για τα αυτοκίνητα. Όλα τα μέρη του δρόμου στο πακέτο του ~i~-οστού φίλου έχουν το ίδιο μήκος ~d_i~.

Δύο διαφορετικοί φίλοι ~a~ και ~b~ μπορούν να συνδέσουν τα γκαράζ τους με έναν δρόμο. Για να χτίσουν αυτόν τον δρόμο, θα πάρουν και οι δύο ένα κομμάτι από το πακέτο τους και θα τα ενώσουν μεταξύ τους, αποκτώντας έτσι δρόμο μήκους ~d_a\;+\;d_b~. Μερικά ζευγάρια φίλων πρόκειται να συνδέσουν τα γκαράζ τους με τον τρόπο που περιγράψαμε, έτσι ώστε τα γκαράζ όλων να είναι συνδεδεμένα. Με άλλα λόγια, ξεκινώντας από οποιοδήποτε γκαράζ θα έπρεπε να είναι δυνατό να φτάσετε σε οποιοδήποτε άλλο γκαράζ χρησιμοποιώντας τους δρόμους.

Ποιο είναι το ελάχιστο συνολικό μήκος δρόμου που χρειάζεται για να γίνει ένα οδικό δίκτυο στο οποίο όλα τα γκαράζ είνα συνδεδεμένα?

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n\;(1 \le n \le 100\,000)~, τον αριθμό των φίλων.

Η επόμενη γραμμή περιέχει ~n~ θετικούς ακέραιους αριθμούς ~d_i\;(1 \le d_i \le 10^9)~, το μήκος των τμημάτων του δρόμου πακέτο του ~i~-οστού φίλου.

Έξοδος

Στη μοναδική γραμμή εκτυπώστε το ελάχιστο συνολικό μήκος δρόμου που απαιτείται για να συνδεθούν όλα τα γκαράζ.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~d_1\;=\;d_2\;=\;\ldots\;=\;d_n~
2	20	~1 \le n \le 1000~
3	20	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

1
10

output

0

Επεξήγηση του 1ου παραδείγματος:

Δεδομένου ότι υπάρχει μόνο ένας φίλος, το γκαράζ του είναι ήδη συνδεδεμένο με τον εαυτό του, επομένως δεν χρειάζεται να χτιστεί κάποιος δρόμος.

input

3
5 5 5
20

output

2
3
4
5

input

4
7 3 3 5

output

24

Επεξήγηση του 3ου παραδείγματος:

Εάν χτιστούν δρόμοι μεταξύ των φίλων 1 και 2, 2 και 3 και μεταξύ 3 και 4, όλοι θα συνδεθούν και το συνολικό κόστος θα είναι ~(7 + 3) + (3 + 3) + (3 + 5) = 24~.