题目描述
Farmer John 正在农场上分发干草堆。
Farmer John 的农场上有 N(1≤N≤2⋅105)座谷仓,分别位于数轴上的整点 x1,…,xN(0≤xi≤106)。Farmer John 正计划将 N 车干草堆运输到整点 y(0≤y≤106),然后为每一座谷仓运输一车干草堆。
不幸的是,Farmer John 的运输系统浪费了很多干草堆。具体来说,给出一些 ai,bi(1≤ai,bi≤106),每车干草堆每向左移动一单位距离,ai 堆干草堆会被浪费;每车干草堆每向右移动一单位距离,bi 堆干草堆会被浪费。形式化地,一车干草堆从整点 y 运动到位于 x 的谷仓,被浪费的干草堆堆数如下:
{ai⋅(y−x)bi⋅(x−y)if y>xif x>y给出 Q(1≤Q≤2⋅105)组相互独立的询问,每组询问给出一组 (ai,bi) 的值,帮助 Farmer John 计算当按照最佳方案选择 y,最少有多少堆干草堆被浪费。
输入格式
第一行包含 N。
接下来一行包含 x1…xN。
接下来一行包含 Q。
接下来 Q 行,每行包含两个整数 ai,bi。
输出格式
输出 Q 行,第 i 行包含第 i 个询问的答案。
提示
样例解释 1
样例中第二个询问,最佳方案为选择 y=2,被浪费的干草堆数量为 2(2−1)+2(2−2)+1(3−2)+1(4−2)+1(10−2)=1+0+1+2+8=13。
测试点性质
- 测试点 2 满足 N,Q≤10。
- 测试点 3 满足 N,Q≤500。
- 测试点 4−6 满足 N,Q≤5000。
- 测试点 7−16 没有额外限制。