Phân Phối Cỏ Khô

Nông dân John cần phân phối cỏ khô cho $N$ chuồng bò nằm tại các vị trí $x_1,x_2,\dots ,x_N$ trên trục số. Ông giao $N$ kiện cỏ đến một điểm tập kết $y$, rồi phân phối mỗi kiện đến một chuồng.

Chi phí vận chuyển kiện cỏ từ điểm $y$ đến chuồng tại vị trí $x$ là:

• $a·(y-x)$ nếu $y\ge x$
• $b·(x-y)$ nếu $x>y$

Với $Q$ truy vấn, mỗi truy vấn cho một cặp $(a,b)$, hãy tìm tổng chi phí tối thiểu khi chọn $y$ tối ưu.

Lưu ý: Mỗi kiện cỏ được giao đến đúng một chuồng, mỗi chuồng nhận đúng một kiện. Tất cả các kiện trong cùng một truy vấn có cùng hệ số $(a,b)$.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$ ($1\le N\le 2·{10}^5$).
• Dòng $2$: $N$ số nguyên $x_1,\dots ,x_N$ ($0\le x_i\le {10}^6$).
• Dòng $3$: Số nguyên $Q$ ($1\le Q\le 2·{10}^5$).
• $Q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a$ và $b$ ($1\le a,b\le {10}^6$).

Dữ liệu ra

In ra $Q$ dòng, mỗi dòng là tổng chi phí tối thiểu cho truy vấn tương ứng.

Ràng buộc

• Test $2$: $N,Q\le 10$.
• Test $3$: $N,Q\le 500$.
• Các test $4$-$6$: $N,Q\le 5000$.
• Các test $7$-$16$: Không có ràng buộc thêm.

Ví dụ