Farmer John은 농장 곳곳에 건초 더미를 나누어 주려고 한다.

Farmer John의 농장에는 \(N\)개의 외양간이 있으며 \((1 \le N \le 200,000)\), 각 외양간은 수직선 위의 정수 좌표 \(x_1,x_2,\dots,x_N\)에 있다. \((0 \le x_i \le 1,000,000)\)

Farmer John은 먼저 \(N\)개의 건초 배송분을 수직선 위의 어떤 정수 좌표 \(y\)에 배달받은 뒤 \((0 \le y \le 1,000,000)\), 각 외양간에 배송분을 하나씩 운반하려고 한다.

하지만 Farmer John이 이용하는 운송 서비스는 건초를 매우 많이 낭비한다. 어떤 \(a_i\), \(b_i\)에 대하여 \((1 \le a_i,b_i \le 1,000,000)\), 배송분 하나를 왼쪽으로 한 칸 운반할 때마다 건초 \(a_i\)개가 낭비되고, 오른쪽으로 한 칸 운반할 때마다 건초 \(b_i\)개가 낭비된다.

좌표 \(y\)에서 좌표 \(x\)에 있는 외양간으로 배송분 하나를 운반할 때 낭비되는 건초의 수는 다음과 같다.

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

가능한 \((a_i,b_i)\)의 값을 나타내는 서로 독립적인 \(Q\)개의 쿼리가 주어진다. \((1 \le Q \le 200,000)\) 각 쿼리마다 \(y\)를 최적으로 선택했을 때 낭비되는 건초의 수의 최솟값을 구하여라.

입력

첫째 줄에 외양간의 수 \(N\)이 주어진다.

둘째 줄에 외양간의 좌표 \(x_1,x_2,\dots,x_N\)이 공백으로 구분되어 주어진다.

셋째 줄에 쿼리의 수 \(Q\)가 주어진다.

다음 \(Q\)개의 줄에 두 정수 \(a_i\)와 \(b_i\)가 공백으로 구분되어 주어진다.

출력

\(Q\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 쿼리의 답을 출력한다.

예제 입력 1

5
1 4 2 3 10
4
1 1
2 1
1 2
1 4

예제 출력 1

11
13
18
30

예제 설명 1

두 번째 쿼리에서는 \(y=2\)를 선택하는 것이 최적이다. 이때 낭비되는 건초의 수는 다음과 같이 \(13\)이다.

\(2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=2+0+1+2+8=13\)

출처

USACO 2023 December Contest, Gold, Problem 3. Haybale Distribution