nh nông dân John đang phân phối các kiện cỏ khô khắp trang trại!

Trang trại của John có \(N\) \((1 \leq N \leq 2 \times 10^5)\) kho chứa, nằm tại các điểm nguyên \(x_1, \dots, x_N\) \((0 \leq x_i \leq 10^6)\) trên trục số. Kế hoạch của John là nhận \(N\) chuyến hàng kiện cỏ khô được chuyển đến một số điểm nguyên \(y\) \((0 \leq y \leq 10^6)\), sau đó phân phối một chuyến hàng đến mỗi kho chứa.

Không may, dịch vụ phân phối của John lại rất lãng phí. Cụ thể, đối với một số \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq 10^6)\), mỗi kiện cỏ bị lãng phí \(a_i\) kiện trên mỗi đơn vị khoảng cách nếu vận chuyển sang trái, và bị lãng phí \(b_i\) kiện trên mỗi đơn vị khoảng cách nếu vận chuyển sang phải. Cụ thể, đối với một kiện hàng được vận chuyển từ điểm \(y\) đến một kho chứa tại điểm \(x\), số kiện cỏ bị lãng phí được tính theo công thức:

Yêu cầu: Với mỗi \(Q\) truy vấn \((1 \leq Q \leq 2 \times 10^5)\), mỗi truy vấn bao gồm các giá trị \((a_i, b_i)\), hãy giúp John tính toán số lượng kiện cỏ bị lãng phí ít nhất có thể nếu anh ta chọn \(y\) một cách tối ưu.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(x_1, \dots, x_N\) mô tả vị trí của các kho chứa trên trục số.
• Dòng thứ ba chứa số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(b_i\) cho mỗi truy vấn.

Output

• In ra \(Q\) dòng, dòng thứ \(i\) chứa kết quả cho truy vấn thứ \(i\).

Scoring

• Subtask 1: \(N, Q \leq 10\)
• Subtask 2: \(N, Q \leq 500\)
• Subtask 3: \(N, Q \leq 5000\)
• Subtask 4: Không có ràng buộc thêm.

Example

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

11
13
18
30