题目描述

有一条向东和向西延伸的道路，$N$ 个人在这条道路上。道路从一个称为原点的点向东和向西无限延伸。

第 $i$ 个人 $(1\leq i\leq N)$ 最初位于原点东侧距离原点 $X_i$ 米处。

这些人可以沿着道路向东或向西移动。具体来说，他们可以执行以下移动任意次数。

选择一个人。如果目的地没有其他人，则将选择的人向东或向西移动 $1$ 米。

注：这里说的目的地指的是，如果这个人要向东移动 $1$ 米，则目的地就是东边 $1$ 米的地方；如果这个人要向西移动 $1$ 米，则目的地就是西边 $1$ 米的地方。

他们总共有 $Q$ 个任务，第 $i$ 个任务 $(1 \leq i \leq Q)$ 描述如下：

第 $T_i$ 个人到达坐标 $G_i$。

找出依次完成所有 $Q$ 个任务所需的最小总移动次数。

输入格式

第一行，一个整数 $N$（$1 \le N \le 2 \times 10^5$）。

第二行，$N$ 个严格升序的整数 $X_1, X_2, \ldots, X_N$，表示初始时每个人所在的位置（$0 \lt X_1 \lt X_2 \lt \ldots \lt X_N \le 10^8$）。

第三行，一个整数 $Q$（$1 \le Q \le 2 \times 10^5$）。

接下来 $Q$ 行，每行包含两个整数 $T_i$ 和 $G_i$，表示一次任务（$1 \le T_i \le N, 0 \le G_i \le 10^8$）。

输出格式

输出一个整数，表示依次完成所有 $Q$ 个任务所需的最小总移动次数。

样例

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

239

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

4294967297

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

89644

说明/提示

样例 1 解释

人员的最佳移动顺序如下（人员的位置不一定按比例绘制）：

对于每个任务，人员的移动如下。

• 第 4 个人向东移动 $6$ 步，第 3 个人向东移动 $15$ 步。
• 第 2 个人向西移动 $2$ 步，第 3 个人向西移动 $26$ 步，第 4 个人向西移动 $26$ 步。
• 第 4 个人向东移动 $18$ 步，第 3 个人向东移动 $18$ 步，第 2 个人向东移动 $18$ 步，第 1 个人向东移动 $25$ 步。
• 第 5 个人向东移动 $13$ 步，第 4 个人向东移动 $24$ 步，第 3 个人向东移动 $24$ 步，第 2 个人向东移动 $24$ 步。

总移动次数为 $21+54+79+85=239$。

你无法以总移动次数 $238$ 或更少完成所有任务，因此打印 239。

数据规模与约定

对于 $30\%$ 的数据：$N,Q \le 2000$，$X_N, G_i \le 10^4$

对于 $100\%$ 的数据：

• $1 \le N,Q \le 2 \times 10^5$
• $0 \lt X_1 \lt X_2 \lt \ldots \lt X_N \le 10^8$
• $1 \le T_i \le N$
• $0 \le G_i \le 10^8$