최적의 골드수급량

게임 league of legends의 프로게임단 T1에는 $N$ ($1 \le N \le 1.5 \cdot 10^5$)명의 프로게이머들이 소속되어 있습니다. 

각 프로게이머들은 게임 내에서 매 분당 골드수급량 $a_1, \dots,a_N$ ($0 \leq a_i \leq 10^8$)의 능력을 가지고 있습니다. 즉, $i$ 번째 프로게이머는 $a_i$ 단위의 골드를 1분당 얻을 수 있습니다.

매일 아침, 모든 $N$명의 프로게이머들은 연습실에서 동시에 연습게임을 진행하고, 관리자는 매 분마다 한 명씩 프로게이머들을 게임에서 제거합니다. 

첫 번째로 제거되는 프로게이머는 게임에 1분 동안 있었으므로, 그의 골드수급량은 $a_x$입니다. 

두 번째로 제거되는 프로게이머는 게임에서 2분 동안 있었으므로, 그의 골드수급량은 $2a_y$입니다. 

세 번째 프로게이머의 골드수급량은 $3a_z$입니다. 그리고 이런 식으로 계속됩니다. 

여기서 $T$는 프로게이머들이 최적의 순서로 게임에서 제거될 때 얻을 수 있는 최대 총 골드수급량을 나타냅니다.

관리자는 프로게이머들의 골드수급량 중 일부가 변경된다면, $T$가 어떻게 변할지 궁금합니다. 

각 $Q$ 쿼리 ($1 \le Q \le 1.5 \cdot 10^5$)에 대해, 각각 두 정수 $i$와 $j$로 지정됩니다. 만약 $a_i$가 $j$ ($0 \leq j \leq 10^8$)로 설정된다면 $T$의 새 값이 무엇이 될 지 계산해 주십시오. 

[주의]

각 쿼리는 다른 쿼리와 무관하게 일시적으로 변경됩니다. 

즉, 다음 쿼리가 고려되기 전에 $a_i$는 원래의 값으로 되돌아갑니다.

첫째 줄에는 $N$이 있습니다.

둘째 줄에는 $a_1 \dots a_N$이 있습니다.

셋째 줄에는 $Q$가 있습니다.

그 다음에 $Q$ 줄 동안 각각 두 개의 공백으로 분리된 정수 $i$와 $j$이 있습니다.

$Q$ 쿼리 각각에 대한 $T$의 값을 각 줄에 따로 출력하십시오.