Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường

Nông dân John có \(N\) \((1 \le N \le {1.5 \times 10^5})\) con bò được đánh số từ \(1\) đến \(N\), con bò \(i\) sản xuất được \(a_i\) \((1 \le a_i \le 10^8, a_i \in \mathbb{Z})\) đơn vị sữa mỗi phút.

Mỗi sáng thức dậy, John bắt đầu với các con bò đang bị xích vào máy vắt sữa trong chuồng, bác ta sẽ thả từng con một ra ngoài để tập thể dục buổi sáng. Con bò đầu tiên được thả sau \(1\) phút vắt sữa, con bò thứ \(2\) được thả sau \(2\) phút vắt sữa, ... Hay nói cách khác, con bò thứ \(i\) được thả sau \(i\) phút vắt sữa, giả sử con bò này được đánh là \(x\) thì sẽ sản xuất được \(a_x \times i\) đơn vị sữa. Gọi \(T\) là lượng sữa lớn nhất mà bác John thu thập được nếu thả các con bò ra theo thứ tự tối ưu.

Bác ta tò mò liệu \(T\) sẽ thay đổi thế nào các một số con bò sản xuất ra lượng sữa khác đi. Có \(Q\) \((1 \le Q \le {1.5 \times 10^5})\) truy vấn, gồm \(2\) số nguyên \(i\) và \(j\), với mỗi truy vấn hãy tính toán \(T\) sẽ thay đổi thế nào nếu \(a_i\) được đặt thành \(j\) \((1 \le j \le 10^8)\). Các truy vấn là độc lập, nghĩa là các truy vấn đều chỉ áp dụng lên trạng thái ban đầu của dãy \(a\).

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(a_1, a_2, ..., a_N\).
• Dòng thứ ba là số \(Q\).
• Trong \(Q\) dòng tiếp theo là \(2\) số nguyên thể hiện mỗi truy vấn.

Output

• In ra giá trị mới của \(T\) cho mỗi truy vấn trên \(Q\) dòng.

Scoring

• Subtask \(1\): \(max(N, Q) \le 1000\).
• Subtask \(2\): Không có ràng buộc gì thêm.

5
1 10 4 2 6
3
2 1
2 8
4 5

55
81
98