건초 배분

Farmer John은 농장 전체에 건초를 나누어 배분하고 있다.

Farmer John의 농장에는 수직선 위의 정수 좌표 $x_1,\dots, x_N$ ($0 \le x_i \le 10^6$)에 위치한 헛간이 $N$개 ($1\le N\le 2\cdot 10^5$) 있다. Farmer John은 먼저 정수 좌표 $y$ ($0 \le y \le 10^6$)로 건초 배송 $N$개를 보내고, 그다음 배송을 헛간마다 하나씩 나누어 준다.

안타깝게도 Farmer John의 배분 서비스는 매우 낭비가 심하다. $a_i$, $b_i$ ($1\le a_i, b_i\le 10^6$)가 주어졌을 때, 배송이 왼쪽으로 한 단위 거리 이동할 때마다 건초 $a_i$개가 낭비되고, 오른쪽으로 한 단위 거리 이동할 때마다 건초 $b_i$개가 낭비된다. 좌표 $y$에서 좌표 $x$의 헛간까지 배송할 때 낭비되는 건초 수는 다음과 같다.

$\begin{cases} 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$번째 질의의 답을 출력한다.