USACO

USACO 2023 December Contest, Gold

Problem 3. Haybale Distribution

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John is distributing haybales across the farm!

Farmer John's farm has $N$ $(1\le N\le 2\cdot 10^5)$ barns, located at integer points $x_1,\dots, x_N$ $(0 \le x_i \le 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 \le y \le 10^6)$ and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some $a_i$ and $b_i$ $(1\le a_i, b_i\le 10^6)$ , $a_i$ haybales are wasted per unit of distance left each shipment is transported, and $b_i$ 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

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

Given $Q$ $(1\le Q\le 2\cdot 10^5)$ independent queries each consisting of possible values of $(a_i,b_i)$ , please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses $y$ optimally.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains

$N$ .

The next line contains $x_1\dots x_N$ .

The next line contains $Q$ .

The next $Q$ lines each contain two integers $a_i$ and $b_i$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Output

$Q$ lines, the

$i$ th line containing the answer for the

$i$ th query.

SAMPLE INPUT:

SAMPLE OUTPUT:

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\le 10$
Input 3: $N,Q\le 500$
Inputs 4-6: $N,Q\le 5000$
Inputs 7-16: No additional constraints.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.