최적의 골드수급량

실행 시간 제한	메모리 제한
4 초	1024 MB

게임 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$ 의 값을 각 줄에 따로 출력하십시오.

55
81
98

첫 번째 쿼리에서 $a$ 는 $[1,1,4,2,6]$ 가 되고, $T =1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55$ 가 됩니다.

두 번째 쿼리에서 $a$ 는 $[1,8,4,2,6]$ 가 되고, $T =1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 6 + 5 \cdot 8 = 81$ 이 됩니다.

세 번째 쿼리에서 $a$ 는 $[1,10,4,5,6]$ 이 되고, $T =1 \cdot 1 + 2 \cdot 4 + 3 \cdot 5 + 4 \cdot 6 + 5 \cdot 10 = 98$ 이 됩니다.

점수: