D - ±1 Operation 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。この A に以下を施すことを「操作」と呼びます。

  • まず、 1 \le i \le N を満たす整数 i を選択する。
  • 次に、以下の 2 つのうちどちらかを選択し、実行する。
    • A_i1 を加算する。
    • A_i から 1 を減算する。

Q 個の質問に答えてください。
i 個目の質問は以下です。

  • 「操作」を 0 回以上何度でも使って A の要素を全て X_i にする時、必要な「操作」の最小回数を求めてください。

制約

  • 入力は全て整数
  • 1 \le N,Q \le 2 \times 10^5
  • 0 \le A_i \le 10^9
  • 0 \le X_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \dots A_N
X_1
X_2
\vdots
X_Q

出力

Q 行にわたって出力せよ。
出力のうち i 行目には、 i 個目の質問に対する答えを整数として出力せよ。


入力例 1

5 3
6 11 2 5 5
5
20
0

出力例 1

10
71
29

A=(6,11,2,5,5) であり、この入力には 3 つの質問が含まれます。

1 つ目の質問について、 A に以下のように 10 回の「操作」を施すことで、 A の要素を全て 5 にすることができます。

  • A_1 から 1 減算する。
  • A_2 から 1 減算することを 6 度繰り返す。
  • A_31 加算することを 3 度繰り返す。

9 回以下の「操作」で A の要素を全て 5 にすることはできません。

2 つ目の質問について、 A71 回の「操作」を施すことで、 A の要素を全て 20 にすることができます。

3 つ目の質問について、 A29 回の「操作」を施すことで、 A の要素を全て 0 にすることができます。


入力例 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

出力例 2

3316905982
2811735560
5542639502
4275864946
4457360498

出力が 32bit 整数に収まらない場合もあります。

Score : 400 points

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.

  • First, choose an integer i such that 1 \le i \le N.
  • Next, choose and do one of the following.
    • Add 1 to A_i.
    • Subtract 1 from A_i.

Answer Q questions.
The i-th question is the following.

  • Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.

Constraints

  • All values in input are integers.
  • 1 \le N,Q \le 2 \times 10^5
  • 0 \le A_i \le 10^9
  • 0 \le X_i \le 10^9

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
X_1
X_2
\vdots
X_Q

Output

Print Q lines.
The i-th line should contain the answer to the i-th question as an integer.


Sample Input 1

5 3
6 11 2 5 5
5
20
0

Sample Output 1

10
71
29

We have A=(6,11,2,5,5) and three questions in this input.

For the 1-st question, you can change every element of A to 5 in 10 operations as follows.

  • Subtract 1 from A_1.
  • Subtract 1 from A_2 six times.
  • Add 1 to A_3 three times.

It is impossible to change every element of A to 5 in 9 or fewer operations.

For the 2-nd question, you can change every element of A to 20 in 71 operations.

For the 3-rd question, you can change every element of A to 0 in 29 operations.


Sample Input 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

Sample Output 2

3316905982
2811735560
5542639502
4275864946
4457360498

The output may not fit into 32-bit integers.