题目描述

农夫约翰有 $N$ 头奶牛，编号 $1∼N$。

其中，第 $i$ 头奶牛的每分钟产奶量为 $a_i$。

每天早上，所有奶牛都会排成一队，逐个被约翰挤奶。

奶牛在队列中的位置越靠前，被挤奶的时间就越短。

排在第 $1$ 位的奶牛被挤奶 $1$ 分钟，排在第 $2$ 位的奶牛被挤奶 $2$ 分钟，依次类推。

也就是说，如果第 $x$ 头奶牛排在队列的第 $y$ 位，则它将被挤奶 $y$ 分钟，总产奶量为 $a_x*y$。

用 $T$ 表示约翰通过合理安排奶牛的排队顺序，可以获得的牛奶总量的最大可能值。

你需要回答 $Q$ 个询问，每个询问给定两个整数 $i,j$，请你回答如果将 $a_i$ 的值变为 $j$，则此时 $T$ 的值是多少。

所有询问之间是相互独立，互不影响的，也就是说，在考虑下一个询问之前，$a_i$ 会恢复到它的初始值。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2...a_N$。

第三行包含整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $i,j$。

输出格式

每个询问输出一行结果，一个整数，表示 $T$ 的值。

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

55
81
98

数据范围

$1≤N≤1.5×10^5$,
$0≤a_i≤10^8,$
$1≤Q≤1.5×10^5，$
$1≤i≤N,$
$0≤j≤10^8$。

样例解释

对于第 1 个询问，$a$ 变为 [1,1,4,2,6]，T==1⋅1+2⋅1+3⋅2+4⋅4+5⋅6=55。

对于第 2 个询问，$a$ 变为 [1,8,4,2,6]，T=1⋅1+2⋅2+3⋅4+4⋅6+5⋅8=81。

对于第 3 个询问，$a$ 变为 [1,10,4,5,6]，T=1⋅1+2⋅4+3⋅5+4⋅6+5⋅10=98。