窄路上的高桥君

题目描述

有一条东西向延伸的道路，路上有 $N$ 个人。 道路以原点为界，向东、向西无限延伸。

第 $i$ 个人 $(1 \le i \le N)$ 最初位于原点以东 $X_i$ 米处。

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

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

他们共有 $Q$ 个任务，第 $i$ 个任务 $(1 \le i \le Q)$ 如下。

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

求按顺序完成全部 $Q$ 个任务所需的最少移动总次数。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$Q$
$T_1$ $G_1$
$T_2$ $G_2$
$\vdots$
$T_Q$ $G_Q$

输出格式

输出答案。

样例

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

239

这些人的一组最优移动序列如下（图中各人的位置不一定按比例绘制）：

对于每个任务，这些人按如下方式移动。

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

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

无法用 $238$ 次或更少的移动总数完成所有任务，因此输出 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 \le N \le 2 \times 10^5$
• $0 \le X_1 \lt X_2 \lt \dotsb \lt X_N \le 10^8$
• $1 \le Q \le 2 \times 10^5$
• $1 \le T_i \le N\ (1 \le i \le Q)$
• $0 \le G_i \le 10^8\ (1 \le i \le Q)$
• 输入中的所有数值均为整数

提示

• 注意，有些人可能需要移动到原点以西或原点以东超过 $10^8$ 米的位置。
• 注意，答案可能超过 $2^{32}$。