← 返回题目列表

Codeforces · 949/B

B. 阵列中的蛙跳

中文机器翻译题面 查看原题

Dima 是一名初级程序员。在他的工作过程中,他经常需要一次又一次地重复以下操作:从数组中删除每一个元素。有一天,他厌倦了这个问题的简单解决方案,他想出了以下奢侈的算法。

让我们考虑最初数组包含从 1 到 n 的 n 个数字,并且数字 i 位于索引为 2i - 1 的单元格中(索引从 1 开始编号),数组的其他单元格为空。每一步 Dima 都会选择一个具有最大索引的非空数组单元格,并将其中写入的数字移动到所选单元格左侧最近的空单元格。该过程继续进行,直到所有 n 个数字都出现在数组的前 n 个单元格中。例如,如果 n = 4,则数组将按如下方式更改:

您必须编写一个程序,允许您确定 Dima 算法完成后索引为 x (1 ≤ x ≤ n) 的单元格中将包含什么数字。

输入

第一行包含两个整数 n 和 q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000)、数组中的元素数量以及查找答案所需的查询数量。

接下来的 q 行包含整数 xi (1 ≤ xi ≤ n),即在 Dima 算法完成后需要输出其内容的单元格索引。

输出

对于 q 个查询中的每一个输出一个整数,该值将在 Dima 算法完成后出现在相应的数组单元中。

示例

输入 #1

4 3
2
3
4

输出 #1

3
2
4

输入 #2

13 4
10
5
4
8

输出 #2

13
3
8
9

注意

第一个示例如图所示。

在第二个示例中,最终数组是 [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7]。