题目描述

$Bob$ 来到农场参观学习，农场有 $n$ 头奶牛，奶牛 $i$ 每分钟的产奶量为 $a_i$ 。

每天挤奶工会给 $n$ 头奶牛连上挤奶器，全部接上挤奶器后，挤奶工播放音乐，奶牛们听着音乐开始产奶。接下来，挤奶工每分钟末会解开一头牛，让其离开，也就是说，第 $1$ 分钟末解开奶牛 $i$, 奶牛 $i$ 生产了 $1$ 分钟的奶，产奶量为 $1*a_i$，第 $2$ 分钟末解开奶牛 $j$，奶牛 $j$ 生产了 $2$ 分钟的奶，产奶量为 $2*a_j$，第 $3$ 分钟末解开奶牛 $k$，奶牛 $k$ 生产了 $3$ 分钟的奶，产奶量为 $3*a_k$ ，依次类推。

$Bob$ 很聪明，他很快的算出每天农场最多的产奶量T。

但产奶工人知道，奶牛有的时候产奶量会有变化，假如有 $q$ 次奶牛的单位时间产奶量发生变化，每次只有 $1$ 头牛产奶量改变，第 $x$ 头牛原来的产奶量 $a_x$ 变为 $y$，挤奶工会重新调整解奶牛的顺序，使得整个农场生产的牛奶最多，挤奶工想考考 $Bob$ 的运算能力，依次计算 $q$ 次变化后农场最多的产奶量T。

注意： 每次变化后，奶牛 $x$ 的产奶量会恢复为原来初始的产奶量。

输入格式

第一行，一个整数 $n$.

第二行，$n$ 个整数表示奶牛一开始单位时间产奶量 $a_i$.

第三行，一个整数 $q$.

接下来 $q$ 行，两个整数 $x$ $y$，表示单位时间产奶量 $a_x$ 变为 $y$.

输出格式

$q$ 行，每行一个整数，表示第 $i$ 变化后，农场最多的产奶量。

6
3 11 4 2 5 2
5
2 1
2 10
6 5
1 2
3 20

73
116
131
119
210

数据规模与约定

所有数据满足： $0 \leq a_i ,y\leq 10^8$,$1\leq x \leq n$

$subtask1$: $1 \leq n,q \leq 10^3$, $30$ 分

$subtask2$: $1 \leq n,q \leq 1.5*10^5$,$70$ 分