分数

题目描述

$N$ 个数排成一排，第 $i$ 个数为 $T_i$。你可以从中标记一些数字，标记完之后，你会获得相应的分数。分数 $=$ (所有满足 $1 \le L \le R \le 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$ 个询问的答案。

样例 #1

样例输入 #1

5
1 1 4 1 1
2
3 2
3 10

样例输出 #1

9
2

样例 #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 \le 100，M = 100$。

对于另外20%的数据，$N \le 1000，M \le 3×10^5$。

对于另外30%的数据，$N \le 3×10^5，M = 10$。

对于100%的数据，$N, M \le 3×10^5$。

$1 \le T_i,X_i \le 10^9$，$T_i$ 之和不超过 $10^{12}$。