题目描述

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。