友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
$N$个数排成一排，第$i$个数为$T_i$。你可以从中标记一些数字，标记完之后，你会获得相应的分数。分数$=$(所有满足$1≤L≤R≤N$且区间$[L,R]$中的数全部被标记的数对$[L,R]$的个数)$-$(被标记的数字之和)。
现在有$M$个询问，第$i$个询问有两个参数$P_i$和$X_i$，你需要求出把$T_{Pi}$变成$X_i$之后能够获得的分数的最大值。每组询问都是独立的。
【输入】
第一行包含一个整数$N$，表示数字个数。
第二行包含$N$个整数，第$i$个数字为$T_i$。
第三行包含一个整数$M$，表示询问个数。
接下来$M$行，每行包含两个整数$P_i$和$X_i$，表示询问的两个参数。
【输出】
输出$M$行，每行一个整数。第$i$个整数表示第$i$个询问的答案。
【输入样例】
5 1 1 4 1 1 2 3 2 3 10
【输出样例】
9 2
【提示】
【样例输入2】
12 1 2 1 3 4 1 2 1 12 3 12 12 10 9 3 11 1 5 35 6 15 12 1 1 9 4 3 10 2 5 1 7 6
【样例输出2】
34 35 5 11 35 17 25 26 28 21
【数据规模】
对于20%的数据，$N≤100，M=100$。
对于另外20%的数据，$N≤1000，M≤3×10^5$。
对于另外30%的数据，$N≤3×10^5，M=10$。
对于100%的数据，$N,M≤3×10^5$。
$1≤T_i,X_i≤10^9$，$T_i$之和不超过$10^{12}$。