题目描述

色拉有一个钱包 \(a_n\)，其中有 \(n\) 张银行卡，第 \(i\) 张卡有 \(a_i\) 美刀的余额，色拉不知道从哪里骗了 \(p\) 刀乐，他想要不被别人发现，因为色拉非常的财迷！

色拉打算把这些美刀藏进去，每次操作可以选择一个银行卡 \(i\) 使得那张卡的美刀余额 \(a_i = a_i + 1\)，一共操作 \(p\) 次。

同时，色拉还想要好朋友饱饱的不满意度最大化！不满意度定义为藏完所有 \(p\) 美刀之后，所有区间的银行卡的余额最大值之和，即 \(\sum_{1 \le i, j \le n}{\max_{i \le k \le j}{a_k}}\)，使得饱饱很羡慕嫉妒有这么多美刀的色拉！

输入格式

第一行一个数 \(t\)，表示数据组数。

对于每组数据，第一行一个数 \(n\)，表示银行卡的数量。

第二行 \(n\) 个数，第 \(i\) 个数 \(a_i\) 表示银行卡 \(i\) 有 \(a_i\) 美刀的余额。

第三行一个数 \(q\)，表示色拉会思考 \(q\) 次对于不同的美刀数量好朋友的最大的不满意度应该是多少！

接下来 \(q\) 行，每一行一个数 \(p\)，表示色拉不知道哪里来的 \(p\) 美刀。

保证 \(t \le 20\)， \(0 \le a_i, p \le 1e5\)， \(n \le 1e3\)， \(q \le 1e3\)，都是整数。

输出格式

对于每组数据的 \(q\) 次询问，每个询问输出一行一个整数表示不满意度最大是多少。注意每次询问之间是独立的。

样例输入

3
3
1 2 3
2
1
2
5
2 2 2 2 2
3
1
2
10
7
11 45 14 19 19 8 10
4
114
514
1919
810

样例输出

17
20
39
48
120
2418
8818
31298
13554