Description

空想用跳棋模拟「圣战」中机凯种的移动方式。

一条无限长的数轴上有 $n$ 个不能动的跳棋，空会询问把一颗可以动的跳棋放在一个位置可以最多进行几次跳跃。空会问很多次，每次询问互相独立。

设第 $i$ 颗不能动的棋子的坐标为 $x_i\left(\forall i\in\left[1,n\right]\right)$.

则跳棋移动的规则如下：

• 这颗跳棋必须是允许移动的。
• 若这颗棋子位于 $a$，目标位置为 $b$，则应仅有一颗棋子位于二个位置之间且中间棋子到 $a,b$ 的距离相等。

形式化的讲应有：

$$\sum_{k=1}^n \left[x_k\in\left[b,a\right]\right]=1$$

且 $\exists k\ x_k=\dfrac{a+b}{2}$.

• 出题人过于良心（，你只能向左边跳。

Input Format

第一行两个整数 $n,q$，同题意。

接下来一行 $n$ 个整数，第 $i$ 个表示 $x_i$。

接下来一行 $q$ 个数 $x_0$，表示放置可以动的棋子的位置。

Output Format

$q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次询问的结果。

3 3
3 5 8
4 6 7

1
2
0

Hint

样例解释 1

$$\Huge\Box\Box\blacksquare{\color{red}{\Box}}\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box\Box$$

从左到右的三个红色方块是询问的位置。

• 对于第一个询问，可以跳 $1$ 步，从 4 跳到 2。
• 对于第二个询问，可以跳 $2$ 步，从 6 跳到 4 跳到 2。
• 对于第三个询问，棋子不能向左移动，因为左边同距离位置有一颗不能动的棋子。

对于 $100\%$ 的数据满足 $1\le n\leq 3\times 10^6$，$1\le q\leq3\times 10^5$，$1\le x\le 10^{18}$，$x_i+1\lt x_{i+1}(\forall i \in [1,n-1])$。

Subtask 编号	$n\le$	$q\le$	时限	空间限制	特殊限制
Subtask 0 (10 pts)	$10^3$		$1000\ \rm\small ms$	$\rm512.00\small\ MB$
Subtask 1 (30 pts)					$\rm A$
Subtask 2 (25 pts)					$\rm B$
Subtask 3 (25 pts)	$3 \times 10^5$		$600\ \rm\small ms$
Subtask 4 (10 pts)

• 限制 $\text{A}$： $x_n\le2\times 10^5$。
• 限制 $\text{B}$：有不超过 $50$ 个 $i$ 不满足 $x_i-x_{i-1}\le 100$ ，其余 $i$ 满足 $\sum_{i}{x_i-x_{i-1}} \le 2\times 10^5$。