← 返回题目列表

AtCoder · abc371_f

I. 窄路高桥

中文机器翻译题面 查看原题

分数: 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