Problemas
농부 존은 농장 전체에 헤이베일을 분배하려고 합니다!
농부 존의 농장에는 N(1≤N≤2⋅10^5)개의 헛간이 있으며, 정수 지점 x1,…,xN(0≤xi≤10^6)에 위치해 있습니다. 농부 존의 계획은 먼저 어떤 정수 지점 y(0≤y≤10^6)으로 N번의 헤이발 배송을 받은 다음 각각의 헛간에 하나의 배송을 분배하는 것입니다.
불행히도, 농부 존의 배송 서비스는 매우 낭비적입니다. 특히 ai와 bi(1≤ai,bi≤10^6)에 대해, 각각의 남아있는 거리 당 ai개의 헤이발이 낭비되고, 각각의 이동 중 오른쪽으로 bi개의 헤이발이 낭비됩니다. 형식적으로, 지점 y에서 x로 이동 중인 배송의 경우 낭비되는 헤이발의 수는 다음과 같습니다.
Q(1≤Q≤2⋅10^5)개의 독립적인 쿼리가 주어지며, 각각은 (ai,bi)의 가능한 값을 포함합니다. 농부 존이 최적으로 y를 선택했을 때 낭비되는 헤이발의 최소량을 계산하는 데 도움을 주세요.
Farmer John is distributing haybales across the farm!
Farmer John's farm has N (1≤N≤2⋅10^5) barns, located at integer points x1,…,xN (0≤xi≤10^6) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10^6) 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≤10^6), 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⋅10^5) 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.
Entrada
첫 번째 줄에는 N이 주어집니다.
다음 줄에는 x1…xN이 주어집니다.
다음 줄에는 Q가 주어집니다.
다음 Q개의 줄 각각에는 두 정수 ai와 bi가 포함되어 있습니다.
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.
Salida
Q개의 줄을 출력하며, 각각의 i번째 줄에는 i번째 쿼리에 대한 답이 있어야 합니다.
Output Q lines, the ith line containing the answer for the ith query.
Ejemplo
5
1 4 2 3 10
4
1 1
2 1
1 2
1 4
11
13
18
30
예를 들어, 두 번째 쿼리에 대한 답을 얻으려면 y=2를 선택하는 것이 최적입니다. 그러면 낭비되는 헤이발의 수는 2(2−1)+2(2−2)+1(3−2)+1(4−2)+1(10−2)=1+0+1+2+8=13입니다.
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.
Debes iniciar sesión para escribir código.