#1383. [USACO23OPEN] Milk Sum S

[USACO23OPEN] Milk Sum S

题目描述

注意:本题的时间限制为 4 秒,是默认时间限制的 2 倍。

Farmer John 的 NN 头奶牛的产奶量为整数 a1,…,aNa_1, \dots, a_N。也就是说,第 ii 头奶牛每分钟产 aia_i 单位的牛奶。

每天早上,Farmer John 会将所有 NN 头奶牛连接到谷仓的挤奶机上。他需要依次断开连接,将奶牛送去进行日常锻炼。第一头奶牛在挤奶 1 分钟后被断开连接,第二头奶牛在再挤奶 1 分钟后被断开连接,依此类推。由于第一头奶牛(假设是奶牛 xx)只在挤奶机上停留了 1 分钟,她总共贡献了 axa_x 单位的牛奶。第二头奶牛(假设是奶牛 yy)在挤奶机上停留了总共 2 分钟,因此贡献了 2ay2a_y 单位的牛奶。第三头奶牛(假设是奶牛 zz)贡献了 3az3a_z 单位的牛奶,依此类推。设 TT 表示 Farmer John 以最优顺序断开奶牛连接时,可以收集到的最大总牛奶量。

Farmer John 很好奇,如果某些奶牛的产奶量发生变化,TT 会如何变化。对于每个由两个整数 ii 和 jj 指定的 QQ 个查询,请计算如果将 aia_i 设置为 jj,新的 TT 值会是多少。注意,每个查询都是独立的临时变化,即在考虑下一个查询之前,aia_i 会恢复为原始值。

输入格式

第一行包含 NN。

第二行包含 a1…aNa_1 \dots a_N。

第三行包含 QQ。

接下来的 QQ 行,每行包含两个用空格分隔的整数 ii 和 jj。

输出格式

请为每个查询输出一行,表示对应的 TT 值。

样例

5
1 10 4 2 6
3
2 1
2 8
4 5
55
81
98

题目来源:洛谷 P9186