103715: [Atcoder]ABC371 F - Takahashi in Narrow Road

Problem Statement

There is a road extending east and west, and $N$ persons are on the road. The road extends infinitely long to the east and west from a point called the origin.

The $i$-th person $(1\leq i\leq N)$ is initially at a position $X_i$ meters east from the origin.

The persons can move along the road to the east or west. Specifically, they can perform the following movement any number of times.

• Choose one person. If there is no other person at the destination, move the chosen person $1$ meter east or west.

They have $Q$ tasks in total, and the $i$-th task $(1\leq i\leq Q)$ is as follows.

• The $T_i$-th person arrives at coordinate $G_i$.

Find the minimum total number of movements required to complete all $Q$ tasks in order.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

239

An optimal sequence of movements for the persons is as follows (the positions of the persons are not necessarily drawn to scale):

For each task, the persons move as follows.

• The 4th person moves $6$ steps east, and the 3rd person moves $15$ steps east.
• The 2nd person moves $2$ steps west, the 3rd person moves $26$ steps west, and the 4th person moves $26$ steps west.
• The 4th person moves $18$ steps east, the 3rd person moves $18$ steps east, the 2nd person moves $18$ steps east, and the 1st person moves $25$ steps east.
• The 5th person moves $13$ steps east, the 4th person moves $24$ steps east, the 3rd person moves $24$ steps east, and the 2nd person moves $24$ steps east.

The total number of movements is $21+54+79+85=239$.

You cannot complete all tasks with a total movement count of $238$ or less, so print 239.

Sample Input 2

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

Sample Output 2

4294967297

Note that some persons may need to move to the west of the origin or more than $10^8$ meters to the east of it.

Also, note that the answer may exceed $2^{32}$.

Sample Input 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

Sample Output 3

89644

问题陈述

有一条东西向延伸的道路，道路上共有$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

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

对于每个任务，人员按以下方式移动。

• 第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。

样本输入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$米到东侧。

另外，请注意答案可能