时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(n\) 堆石子,每堆石子的石子数分别为 \(a[1],a[2],…,a[n]\)，每次你可以把第 \(i\) 堆合并到第 \(j\) 堆，合并后第 \(j\) 堆的石子数为 \(a[i]+a[j]\)，第 \(i\) 堆消失，这样操作的代价为 \(a[i]\) ，总代价为每次操作的代价之和。你的任务是找出把 \(n\) 堆石子合并为一堆的最小代价。

　　为了增加点挑战性，规定一堆石子只能与其他堆合并 \(k\) 次（如果某堆已经合并了 \(k\) 次以后就只能被合并到其他堆了）。我会给出 \(q\) 个这样的 \(k\)，不过相信你还是可以 AC 的~

【输入格式】

　　第一行一个数 \(n\)。
　　第二行 \(n\) 个数,表示 \(a[i]\)。
　　第三行一个数 \(q\)，表示有 \(q\) 个询问。
　　第四行 \(q\) 个数表示 \(q\) 个询问的 \(k\)。

【输出格式】

　　输出 \(q\) 个整数，即对每个 \(k\) 的最小代价

【输入输出样例】

　Input

5
2 3 4 1 1
2
2 3

　Output

9 8

【数据说明】

　　对于 \(100\%\) 的数据，\(≤ n,q,k ≤ 10^5\)，\(0 ≤ a[i] ≤ 10^9\)

【来源】

　　Mr.he