分数: 550 点
问题陈述
有一条东西向的路,并且 N 有人在路上。 这条路从一个称为原点的点向东和向西延伸无限长。
的 树的 i第人 (1\leq i\leq N) 最初位于某个位置 X_i 距原点以东米。
人们可以沿着道路向东或向西移动。 具体来说,他们可以多次执行以下动作。
- 选择一个人。 如果目的地没有其他人,移动选定的人 1 向东或向西米。
他们有 Q 任务总数,以及 i- 第一个任务 (1\leq i\leq Q) 如下。
- 的 树的 T_i第人到达坐标 G_i.
找出完成所有动作所需的最小总动作数 Q 任务按顺序排列。
约束
- 1\leq N\leq2\times10^5
- 0\leq X_1 < X_2 < \dotsb < X_N \leq10^8
- 1\leq Q\leq2\times10^5
- 1\leq T_i\leq N\ (1\leq i\leq Q)
- 0\leq G_i\leq10^8\ (1\leq i\leq Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 X_2 \ldots X_N Q T_1 G_1 T_2 G_2 \vdots T_Q G_Q
输出
打印答案。
示例输入 1
5 10 20 30 40 50 4 3 45 4 20 1 35 2 60
示例输出 1
239
人员的最佳移动顺序如下(人员的位置不一定按比例绘制):

对于每项任务,人员移动如下。
- 第四人移动 6 向东迈步,第三个人移动 15 向东迈步。
- 第二个人移动 2 向西走,第三个人移动 26 向西走,第四个人移动 26 向西迈步。
- 第四人移动 18 向东迈步,第三个人移动 18 向东走,第二个人移动 18 向东迈步,第一个人移动 25 向东迈步。
- 第5人移动 13 向东迈步,第四个人移动 24 向东迈步,第三个人移动 24 向东走,第二个人移动 24 向东迈步。
总移动次数为 21+54+79+85=239.
您无法完成总移动次数为 238 或更少,因此打印 239.
示例输入 2
8 0 1 2 3 4 5 6 100000000 6 1 100000000 8 0 1 100000000 8 4 1 100000000 5 21006578
示例输出 2
4294967297
请注意,有些人可能需要移动到原点以西或超过 10^8 米处。
另外,请注意,答案可能会超过 2^{32}.
示例输入 3
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
示例输出 3
89644