B. Сахилгагүй овоон дараалал

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

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

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

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

Таны өмнө $a_1, a_2, ... , a_n$ гэх $n$ элементтэй овоон дараалал байна.

Та нэг үйлдлээр $i$ овоог $j$-р овоонд нэмж чадна. Энэ үед $j$ овооны хэмжээ $i$ овооны хэмжээгээр нэмэгдэх юм. Уг үйлдэл нь нэмж буй овооны хэмжээтэй тэнцүү үнэтэй.

Таны даалгавар бол бүх овоог нийлүүлэхад гарах хамгийн бага үнийг олох явдал юм.

Даалгаврыг хүндрүүлэхийн тулд овоо бүрт хамгийн ихдээ хэдэн овоог нэмж болохыг илэрхийлэх $k$ тоо өгөгдсөн. Уг тооноос хэтэрвэл та уг овоог зөвхөн өөр овоон дээр л нэмж чадна.

Уг бодлогыг улам хүндрүүлэхийн тулд танд хэд хэдэн $k$-н утганд (бүгд ялгаатай байх албагүй) хамгийн бага утгыг олохыг даалгажээ. Нийт $q$ удаа хүсэлт өгөгдөнө.

Оролт

Эхний мөрөнд нийт овооны тоо $n$ ($1 ≤ n ≤ 10^5$) өгөгдөнө. Дараагийн мөрөнд овооны хэмжээг илэрхийлэх $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^9$) болох нийт $n$ тоо өгөгдөнө.

Гуравдугаар мөрөнд хүсэлтийн тоо $q$ ($1 ≤ q ≤ 10^5$) байна. Сүүлийн мөрөнд хүсэлт бүрийг илэрхийлэх $k_1, k_2, ... , k_q$ ($1 ≤ k_i ≤ 10^5$) байна. Энд $k_i$ давтагдаж болохыг анхаараарай.

Гаралт

Хүсэлтүүдийн хариуг оролтонд өгөгдсөн дарааллаар хэвлэ. Нийт $q$ ширхэг тоо хэвлэх юм.

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

Орчуулсан: zoloogg

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

Оролт
5
2 3 4 1 1
2
2 3
Гаралт
9 8 

Тэмдэглэл

In the first sample one way to get the optimal answer goes like this: we add in turns the $4$-th and the $5$-th piles to the $2$-nd one; then we add the $1$-st pile to the $3$-rd one; we add the $2$-nd pile to the $3$-rd one. The first two operations cost $1$ each; the third one costs $2$, the fourth one costs $5$ (the size of the $2$-nd pile after the first two operations is not $3$, it already is $5$).

In the second sample you can add the $2$-nd pile to the $3$-rd one (the operations costs $3$); then the $1$-st one to the $3$-th one (the cost is $2$); then the $5$-th one to the $4$-th one (the costs is $1$); and at last, the $4$-th one to the $3$-rd one (the cost is $2$).

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