← 返回题目列表

AtCoder · bitflyer2018_final_b

B. 交通费

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

配点 : 400 点

問題文

你是现场竞赛的运行负责人。 该竞赛的参与者有 N 人,1, 2, ..., N 已被编号。 参加者 i 是 x 轴上座的标 X_i 居住的位置。

你正在考虑向比赛的参与者支付前往会场的交通费。 参加者 i 的支付金额,根据比赛会场的位置 c 和基准值 d 定如下。

  • |X_i - c| \leq d 时,|X_i - c| 円
  • 否则,d 円

会场的位置 c 和基准值 d 在确定时,Q 对这些种类值的候选,决定计算给予参加者的交通费总额。

整数 C_1, C_2, ..., C_Q 以及 D_1, D_2, ..., D_Q 。 i = 1, 2, ..., Q 对于,c = C_i, d = D_i 当设为时,请求出给予参加者的交通费总额。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_i < X_{i + 1} (1 \leq i < N)
  • 1 \leq Q \leq 10^5
  • 0 \leq C_i, D_i \leq 10^9 (1 \leq i \leq Q)
  • 所有输入值均为整数。

入力

输入是按以下格式从标准输入给出的。

N Q
X_1 X_2 ... X_N
C_1 D_1
C_2 D_2
:
C_Q D_Q

出力

Q 行。 其中 i 行目 (1 \leq i \leq Q)有 当c = C_i, d = D_i 时打印答案。


入力例 1

5 3
1 5 10 20 30
7 3
10 20
100 10

出力例 1

14
44
50

例如,c 的数值 C_1 = 7 如果设置d 的数值 D_1 = 3 , 每个参与者将有自己的交通费用。 3 円、2 円、3 円、3 円、3 将支付日元。 因此 1 行中, 3 + 2 + 3 + 3 + 3 =14 。


入力例 2

6 3
0 1 2 999999998 999999999 1000000000
0 0
100 99
1000000000 1000000000

出力例 2

0
593
3000000000

入力例 3

7 5
590 593 633 642 743 859 872
642 850108511
743 153
633 20
642 0
842 60895346

出力例 3

658
759
109
0
1056