/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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\lt X _ 2\lt\dotsb\lt 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+1 メートル以上東に進んだところに移動する必要がある場合があることに注意してください。
また、答えが 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
Score : 550 points
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