06715. USACO·产奶总和 未做

注意：本题的时限为 4 秒，为默认时限的 2 倍。

Farmer John 的 $N$ 头奶牛（$1\le N\le 1.5\cdot 10^5$）拥有整数产奶量 $a_1,\dots ,a_N$。也就是说，第 $i$ 头奶牛每分钟产 $a_i$ 单位的牛奶，其中 $0\le a_i\le 10^8$。

每天早上，Farmer John 让全部 $N$ 头奶牛都接上谷仓里的挤奶机。他必须逐头解开她们，把她们放出去进行每日的锻炼。他放出的第一头奶牛在挤奶 1 分钟后就被解开，第二头放出的奶牛又挤了 1 分钟后被解开，依此类推。由于第一头奶牛（设为第 $x$ 头）在挤奶机上只待了 1 分钟，她总共只贡献 $a_x$ 单位的牛奶；第二头奶牛（设为第 $y$ 头）在挤奶机上总共待了 2 分钟，因此贡献 $2a_y$ 单位的牛奶；第三头奶牛（设为第 $z$ 头）总共贡献 $3a_z$ 单位，依此类推。设 $T$ 表示 Farmer John 以最优顺序解开奶牛时，能够收集到的牛奶总量最大值。

Farmer John 好奇：如果牛群中某些产奶量发生了变化，$T$ 会受到怎样的影响。对于 $Q$（$1\le Q\le 1.5\cdot 10^5$）次询问中的每一次，每次由两个整数 $i$ 和 $j$ 指定，请计算如果将 $a_i$ 设为 $j$（$0\le j\le 10^8$），新的 $T$ 值会是多少。注意，每次询问考虑的都是一个独立的、暂定的改动，与其他询问无关；也就是说，在考虑下一次询问之前，$a_i$ 会恢复为其原始值。

第一行包含 $N$。

第二行包含 $a_1\dots a_N$。

第三行包含 $Q$。

接下来 $Q$ 行，每行包含两个空格分隔的整数 $i$ 和 $j$。

对 $Q$ 次询问中的每一次，各输出一行对应的 $T$ 值。

【样例解释】

对于第一次询问，$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：无额外限制。