Milk Sum

Farmer John có $N$ con bò, con bò thứ $k$ có giá trị sản xuất sữa là $a_k$. Mỗi sáng, ông chọn một thứ tự để thả bò ra đồng. Con bò được thả ra thứ $i$ (trong số $N$ con) sẽ đóng góp lượng sữa bằng $i\times a_k$ (với $a_k$ là giá trị sản xuất sữa của con bò đó).

Tổng lượng sữa $T$ phụ thuộc vào thứ tự thả. Farmer John muốn chọn thứ tự thả để tối đa hóa $T$.

Cho $Q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $i$ và $j$, nghĩa là: nếu tạm thời đổi giá trị sản xuất sữa của con bò thứ $i$ thành $j$, thì tổng lượng sữa tối đa $T$ là bao nhiêu? Các truy vấn độc lập — mỗi truy vấn chỉ thay đổi tạm thời, không ảnh hưởng đến các truy vấn khác.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$.
• Dòng thứ ba chứa số nguyên $Q$.
• $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $j$.

Dữ liệu ra

In $Q$ dòng, mỗi dòng là giá trị $T$ tối đa tương ứng với truy vấn đó.

Ràng buộc

• $1\le N\le 1.5\times {10}^5$
• $0\le a_k\le {10}^8$
• $1\le Q\le 1.5\times {10}^5$
• $1\le i\le N$, $0\le j\le {10}^8$

Ví dụ