English · Original
Chinese · Translation
Formal · Original
Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.
Let's consider that initially array contains _n_ numbers from 1 to _n_ and the number _i_ is located in the cell with the index 2_i_ - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all _n_ numbers will appear in the first _n_ cells of the array. For example if _n_ = 4, the array is changing as follows:
<center></center>You have to write a program that allows you to determine what number will be in the cell with index _x_ (1 ≤ _x_ ≤ _n_) after Dima's algorithm finishes.
## Input
The first line contains two integers _n_ and _q_ (1 ≤ _n_ ≤ 1018, 1 ≤ _q_ ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.
Next _q_ lines contain integers _x__i_ (1 ≤ _x__i_ ≤ _n_), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.
## Output
For each of _q_ queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.
[samples]
## Note
The first example is shown in the picture.
In the second example the final array is \[1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7\].
Dima 是一名编程新手。在编程过程中，他经常需要重复执行以下操作：从数组中移除每个第二个元素。一天，他厌倦了这个问题的简单解法，于是提出了以下夸张的算法。
假设初始时数组包含 #cf_span[n] 个数字，从 #cf_span[1] 到 #cf_span[n]，且数字 #cf_span[i] 位于索引为 #cf_span[2i - 1] 的单元格中（索引从 1 开始计数），其余单元格为空。每一步，Dima 选择索引最大的非空单元格，并将其中的数字移动到其左侧最近的空单元格中。该过程持续进行，直到所有 #cf_span[n] 个数字都出现在数组的前 #cf_span[n] 个单元格中。例如，当 #cf_span[n = 4] 时，数组的变化过程如下：
你需要编写一个程序，能够在 Dima 的算法结束后，确定索引为 #cf_span[x]（#cf_span[1 ≤ x ≤ n]）的单元格中的数字。
第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 1018]，#cf_span[1 ≤ q ≤ 200 000]），分别表示数组中的元素个数和需要回答的查询个数。
接下来的 #cf_span[q] 行每行包含一个整数 #cf_span[xi]（#cf_span[1 ≤ xi ≤ n]），表示需要输出 Dima 算法结束后对应单元格中数值的索引。
对于每个 #cf_span[q] 个查询，请输出一个整数，表示 Dima 算法结束后对应数组单元格中的数值。
第一个例子如图所示。
在第二个例子中，最终数组为 #cf_span[[1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7]]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 1018]，#cf_span[1 ≤ q ≤ 200 000]），分别表示数组中的元素个数和需要回答的查询个数。接下来的 #cf_span[q] 行每行包含一个整数 #cf_span[xi]（#cf_span[1 ≤ xi ≤ n]），表示需要输出 Dima 算法结束后对应单元格中数值的索引。
## Output
对于每个 #cf_span[q] 个查询，请输出一个整数，表示 Dima 算法结束后对应数组单元格中的数值。
[samples]
## Note
第一个例子如图所示。在第二个例子中，最终数组为 #cf_span[[1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7]]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ n \leq 10^{18} $, be the number of elements.
Let the initial configuration be an infinite array where element $ i \in \{1, \dots, n\} $ is placed at index $ 2i - 1 $, and all other indices are empty.
Let the process be defined recursively:
At each step, select the rightmost non-empty cell with index $ j $, and move its element to the nearest empty cell to the left. Repeat until all $ n $ elements occupy the first $ n $ cells (indices $ 1 $ to $ n $).
Let $ f_n : \{1, \dots, n\} \to \{1, \dots, n\} $ be the final position function: $ f_n(x) $ = the final index in $ [1, n] $ occupied by the number $ x $.
Let $ g_n : \{1, \dots, n\} \to \{1, \dots, n\} $ be the inverse: $ g_n(i) $ = the number located at final index $ i $.
**Constraints**
1. $ 1 \leq n \leq 10^{18} $
2. $ 1 \leq q \leq 200{,}000 $
3. For each query $ x_i $, $ 1 \leq x_i \leq n $
**Objective**
For each query $ x_i $, compute $ g_n(x_i) $, the number residing at final index $ x_i $ after the process terminates.
API Response (JSON)
{
"problem": {
"name": "B. A Leapfrog in the Array",
"description": {
"content": "Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF949B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Dima 是一名编程新手。在编程过程中，他经常需要重复执行以下操作：从数组中移除每个第二个元素。一天，他厌倦了这个问题的简单解法，于是提出了以下夸张的算法。\n\n假设初始时数组包含 #cf_span[n] 个数字，从 #cf_span[1] 到 #cf_span[n]，且数字 #cf_span[i] 位于索引为 #cf_span[2i - 1] 的单元格中（索引从 1 开始计数），其余单元格为空。每...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 10^{18} $, be the number of elements. \nLet the initial configuration be an infinite array where element $ i \\in \\{1, \\dots, n\\} $ is placed at i...",
"is_translate": false,
"language": "Formal"
}
]
}