Muallif: __thecrash__
D. Printer navbati
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Informatika xonasida bitta printer bor. Dars tugashiga oz qolganda \(n\) nafar o'quvchi uyga vazifasini chop etish uchun printerga keldi. \(i\)-o'quvchining hujjatini chop etish \(t_i\) soniya davom etadi.
Printer bir vaqtda faqat bitta hujjatni chop etadi. Hujjatlar ketma-ket, orada tanaffussiz chop etiladi, birinchi hujjat \(0\)-soniyada boshlanadi. Har bir o'quvchi o'z hujjati to'liq chop etilib bo'lgach darhol uyga ketadi. O'quvchining kutish vaqti deb, \(0\)-soniyadan uning hujjati tayyor bo'lguncha o'tgan vaqtga aytiladi.
O'qituvchi hujjatlarni istalgan tartibda chop etishi mumkin. U barcha o'quvchilarning kutish vaqtlari yig'indisi eng kichik bo'lishini xohlaydi. Shu eng kichik yig'indini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — o'quvchilar soni.
Ikkinchi qatorda \(n\) ta butun son \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^6\)) — har bir hujjatni chop etish vaqti.
Chiquvchi ma'lumotlar
Bitta son — kutish vaqtlari yig'indisining eng kichik qiymati.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
3 3 1 2 |
10 |
2 |
4 5 5 5 5 |
50 |
3 |
1 1000000 |
1000000 |
Izoh
Birinchi misolda hujjatlarni \(1\), \(2\), \(3\) soniyalik tartibda chop etish kerak. Shunda ular \(1\)-, \(3\)- va \(6\)-soniyalarda tayyor bo'ladi va yig'indi \(1 + 3 + 6 = 10\) bo'ladi. Agar berilgan tartibda, ya'ni \(3\), \(1\), \(2\) deb chop etilsa, hujjatlar \(3\)-, \(4\)- va \(6\)-soniyalarda tayyor bo'ladi va yig'indi \(13\) ga teng bo'ladi.