F. Нэгийг худалдаж аваад, Нэгийг үнэгүй аваарай

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ойролцоох жигнэмгний дэлгүүр онцгой хямдрал зарласан байгаа. Үнийг нь бүтэн төлсөн жигнэмэг бүртээ түүнээс эрс хямд үнэтэй жигнэмгийн үнэгүй авч болно. Таны авахыг хүсч буй бүх жигнэмгний үнэ өгөгдсөн бөгөөд тэр жигнэмэгүүдийг авахад төлөх мөнгөний хамгийн бага хэмжээг тодорхойл.

Оролт

Оролт таны авахыг хүсч буй жигнэмэгний тоо болох $n$ ($1 ≤ n ≤ 500000$) ширхэг бүхэл тоогоор эхлэнэ. Удаах мөр нь тус бүр жигнэмэгний үнийг илэрхийлж буй $n$ ширхэг бүхэл тоог агуулна. Бүх үнүүд $10^9$-өөс хэтрэхгүй эерэг бүхэл тоонууд болно.

Гаралт

Авахыг хүсч буй бүх жигнэмэгний хамгийн бага үнийг хэвлэнэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Энхдүүрэн

Жишээ тэстүүд

Оролт
6
3 4 5 3 4 5
Гаралт
14
Оролт
5
5 5 5 5 5
Гаралт
25
Оролт
4
309999 6000 2080 2080
Гаралт
314159

Тэмдэглэл

In the first test case you can pay for a pie with cost 5 and get a pie with cost 4 for free, then pay for a pie with cost 5 and get a pie with cost 3 for free, then pay for a pie with cost 4 and get a pie with cost 3 for free.

In the second test case you have to pay full price for every pie.

Сэтгэгдлүүдийг ачааллаж байна...