$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\n1 2 1 3 4 1 2 1 12 3 12 12\n10\n9 3\n11 1\n5 35\n6 15\n12 1\n1 9\n4 3\n10 2\n5 1\n7 6
【样例输出2】
34\n35\n5\n11\n35\n17\n25\n26\n28\n21
【数据规模】
对于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}$。