102553: [AtCoder]ABC255 D - ±1 Operation 2

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.

问题描述

你得到一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。对这个序列进行以下操作称为一个 操作。

• 首先，选择一个整数 $i$，满足 $1 \le i \le N$。
• 接下来，选择并执行以下一项操作。
  • 将 $A_i$ 加 $1$。
  • 将 $A_i$ 减 $1$。

回答 $Q$ 个问题。

第 $i$ 个问题是以下内容。

• 考虑对 $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)$ 和三个问题。

对于第 $1$ 个问题，你可以在 $10$ 次操作中将 $A$ 中的每个元素都变成 $5$，如下所示。

• 将 $A_1$ 减 $1$。
• 将 $A_2$ 减 $1$ 六次。
• 将 $A_3$ 加 $1$ 三次。

不可能在 $9$ 次或更少的次数中将 $A$ 中的每个元素都变成 $5$。

对于第 $2$ 个问题，你可以在 $71$ 次操作中将 $A$ 中的每个元素都变成 $20$。

对于第 $3$ 个问题，你可以在 $29$ 次操作中将 $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

输出可能不适合 $32$ 位整数。