Nhân dịp trung thu sắp tới, Thái sẽ phân phát bánh trung thu cho mọi người trong thành phố. Thành phố có ~N~ xưởng phân phát của Thái nằm trên một trục đường thẳng, xưởng thứ ~i~ nằm ở vị trí ~x_i~. Kế hoạch của Thái là đầu tiên anh ấy sẽ có ~N~ chiếc xe tập trung tại một điểm ~y~ nào đó trên trục đó, xong rồi từ đó mỗi xe sẽ đến một xưởng phân phát.

Tuy nhiên trong quá trình vận chuyển lại xảy ra vấn đề nghiêm trọng. Cụ thể, với ~a_i~ và ~b_i~ cho trước, mỗi đơn vị khoảng cách xe đi về bên trái từ vị trí xuất phát thì lại làm rơi ~a~ chiếc bánh, mỗi đơn vị khoảng cách xe đi về bên phải từ vị trí xuất phát thì lại làm rơi ~b~ chiếc bánh.

Hay nói cách khác, nếu một chiếc xe đi từ vị trí ~y~ đến vị trí ~x_i~ thì số chiếc bánh làm rơi sẽ là:

• ~a*(y-x_i)~ nếu ~y \ge x_i~;

• ~b*(x_i-y)~ nếu ~x_i > y~.

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số ~a~ và ~b~, hãy giúp Thái tính xem với ~a~ và ~b~ như vậy thì số lượng chiếc bánh tối thiểu bị rơi ra là bao nhiêu nếu chọn điểm ~y~ tối ưu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ — số lượng xưởng phân phát.

• Dòng thứ hai chứa ~N~ số nguyên ~x_1, x_2, \dots, x_N~ (~1 \le x_i \le 10^6~), trong đó ~x_i~ là vị trí xưởng thứ ~i~.

• Dòng thứ ba chứa số nguyên ~Q~ — số lượng truy vấn.

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a~ và ~b~ (~1 \le a, b \le 10^6~).

Output

Ghi ra ~Q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input 1

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

Sample Output 1

11
13
18
30

Notes

Giải thích:

Ở truy vấn thứ hai với ~a=2, b=1~, nếu chọn ~y=2~ thì tổng số bánh bị rơi là ~2*(2-1)+2*(2-2)+1*(3-2)+1*(4-2)+1*(10-2)=13~.

Giới hạn:

• ~25\%~ số điểm: ~1 \le N, Q \le 10~;

• ~25\%~ số điểm: ~1 \le N, Q \le 500~;

• ~20\%~ số điểm: ~1 \le N, Q \le 5000~;

• ~30\%~ số điểm: ~1 \le N, Q \le 2 \cdot 10^5~.