P7894 'JROI-3' 1÷0

``` 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. ```

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).

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 $q$ lines. Each line contains an integer. The $i$-th line is the answer to the $i$-th query.

#### 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$ | $10^3$ | $1000\ \rm\small ms$ | $\rm512.00\small\ MB$ | | | Subtask 1 (30 pts) | | | $1000\ \rm\small ms$ | $\rm512.00\small\ MB$ | $\rm A$ | | Subtask 2 (25 pts) | | | $1000\ \rm\small ms$ | $\rm512.00\small\ MB$ | $\rm B$ | | Subtask 3 (25 pts) | $3 \times 10^5$ | | $600\ \rm\small ms$ | $\rm512.00\small\ MB$ | | | Subtask 4 (10 pts) | | | $600\ \rm\small ms$ | $\rm512.00\small\ MB$ | | - 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