Background

1÷0=梦恋

   On a distant hill, you can see a scene as if the heavens and the earth are collapsing.

    "——A report has come from the 'Design Entity'——Design successfully reproduced at power '72.8%'——Begin synchronization."

    One female body of the Ex-Machina said this to Riku, then raised her hand.

    "【Tenka】——Org.0000——'True Canon · Star-Slayer'——Please."

    ——What appeared in the void was something that looked like a small tower, a spear stuck into the ground.

    What was just witnessed was a violent vortex that seemed to end the world.

Problem Description

Sora uses checkers to simulate the movement of the Ex-Machina in the "Holy War".

On an infinite number line, there are $n$ immovable checkers. Sora will ask: if you place one movable checker at a position, how many jumps can it make at most. Sora will ask many times, and each query is independent.

Let the coordinate of the $i$-th immovable checker be $x_i\left(\forall i\in\left[1,n\right]\right)$.

The movement rules are as follows:

• This checker must be movable.
• If the checker is at $a$ and the target position is $b$, then there must be exactly one checker between the two positions, and the distance from the middle checker to $a$ and $b$ must be equal.

Formally, it should satisfy:

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

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

• The problem setter is too kind (so you can only jump to the left).

Input Format

The first line contains two integers $n,q$, as described.

The next line contains $n$ integers; the $i$-th one is $x_i$.

The next line contains $q$ numbers $x_0$, meaning the position where the movable checker is placed.

Output Format

Output $q$ lines. Each line contains an integer. The $i$-th line is the answer to the $i$-th query.

3 3
3 5 8
4 6 7

1
2
0

Hint

Sample Explanation 1

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

The three red squares from left to right are the query positions.

• For the first query, it can jump $1$ step, from 4 to 2.
• For the second query, it can jump $2$ steps, from 6 to 4 to 2.
• For the third query, the checker cannot move left, because there is an immovable checker at the position with the same distance on the left.

For $100\%$ of the testdata, $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 ID	$n\le$	$q\le$	Time Limit	Memory Limit	Special Limit
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)

• Constraint $\text{A}$: $x_n\le2\times 10^5$.
• Constraint $\text{B}$: There are no more than $50$ indices $i$ that do not satisfy $x_i-x_{i-1}\le 100$. For the remaining $i$, it satisfies $\sum_{i}{x_i-x_{i-1}} \le 2\times 10^5$.

Translated by ChatGPT 5