Farmer John is distributing haybales across the farm!
Farmer John's farm has N (1≤N≤2⋅105) barns, located at integer points x1,…,xN (0≤xi≤106) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤106) and then distribute one shipment to each barn.
Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some ai and bi (1≤ai,bi≤106), ai haybales are wasted per unit of distance left each shipment is transported, and bi haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by
Given Q(1≤Q≤2⋅105) independent queries each consisting of possible values of (ai ,bi ), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.
INPUT FORMAT (pipe stdin):
The first line contains N.
The next line contains x1…xN.
The next line contains Q.
The next Q lines each contain two integers ai and bi.
OUTPUT FORMAT (pipe stdout):
Output Q lines, the i th line containing the answer for the ith query.
SAMPLE INPUT:
5
1 4 2 3 10
4
1 1
2 1
1 2
1 4
SAMPLE OUTPUT:
11
13
18
30
For example, to answer the second query, it is optimal to select y=2
. Then the number of wasted haybales is equal to 2(2−1)+2(2−2)+1(3−2)+1(4−2)+1(10−2)=1+0+1+2+8=13.
SCORING:
Input 2: N,Q≤10
Input 3: N,Q≤500
Inputs 4-6: N,Q≤5000
Inputs 7-16: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
