注意：此问题的时间限制为4s，默认为2x

题目描述

农夫John的$N$奶牛（$1\le N\le 1.5\cdot 10^5$）的产奶量为$a_1，\dots，a_N$。也就是说，第$i$头牛每分钟产$a_i$单位的牛奶，其中$0 \leq a_i\leq10^8$。

每天早上，农夫约翰都会把$N$头奶牛连接到谷仓里的挤奶机上。他被要求一个接一个地给他们挤奶，再把它们送出去进行日常锻炼。他送出去的第一头牛在挤奶1分钟后就被离开了，他送出来的第二头牛在挤奶2分钟后就离开了，以此类推。由于第一头牛（比如奶牛$x$）只在挤奶机上呆了一分钟，所以她只贡献了$a_x$单位的总奶量。第二头奶牛（比如奶牛$y$）在挤奶机上总共花费了两分钟，因此贡献了$2a_y$单位的总牛奶。第三头奶牛（比如奶牛$z$）贡献了$3a_z$的总单位，依此类推。令$T$代表农夫John如果以最佳顺序给奶牛挤奶，可以收集的最大可能牛奶总量。

农民约翰很好奇，如果他的牛群中的一些牛奶生产价值不同，新的$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$值。

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

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$。

数据范围

输入2-4:$N，Q\le 1000$

输入5-11：无额外限制。

问题学分：Benjamin Qi