分数

【题目描述】

$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}$。

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

34\n35\n5\n11\n35\n17\n25\n26\n28\n21