06722. USACO·干草分发选址 未做

Farmer John 正在全农场分发干草捆！

Farmer John 的农场有 $N$（$1\le N\le 2\cdot 10^5$）座牛棚，位于数轴上的整点 $x_1,\dots ,x_N$（$0\le x_i\le 10^6$）。Farmer John 的计划是先把 $N$ 批干草捆运送到某个整点 $y$（$0\le y\le 10^6$），然后把每一批分发给一座牛棚。

不幸的是，Farmer John 的配送服务非常浪费。具体来说，对某个 $a_i$ 和 $b_i$（$1\le a_i,b_i\le 10^6$），每批干草捆每向左运输一个单位距离会浪费 $a_i$ 个干草捆，每向右运输一个单位距离会浪费 $b_i$ 个干草捆。形式化地，对于一批从点 $y$ 运往位于点 $x$ 的牛棚的干草捆，浪费的干草捆数量由下式给出：

a_i\cdot (y-x) & \text{if } y \ge x \
b_i\cdot (x-y) & \text{if } x > y
\end{cases}.$$

给定 $Q$（$1\le Q\le 2\cdot 10^5$）组独立的询问，每组询问给出一组可能的 $(a_i,b_i)$ 值，请帮助 Farmer John 求出：如果他最优地选择 $y$，最少会浪费多少干草捆。

第一行包含 $N$。

接下来一行包含 $x_1\dots x_N$。

接下来一行包含 $Q$。

接下来 $Q$ 行每行包含两个整数 $a_i$ 和 $b_i$。

输出 $Q$ 行，第 $i$ 行包含第 $i$ 组询问的答案。

【样例解释】

例如，回答第二组询问时，最优方案是选择 $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\le 10$

• 测试点 3：$N,Q\le 500$

• 测试点 4-6：$N,Q\le 5000$

• 测试点 7-16：无附加限制。