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}^+ $, $ q \in \mathbb{Z}^+ $.
Let $ A $ be an array of length $ 2n - 1 $, initially with $ a_{2i-1} = i $ for $ i = 1, \dots, n $, and all other cells empty.
**Process**
Repeatedly:
- Select the rightmost non-empty cell at index $ j $.
- Move its value to the nearest empty cell to the left.
- Continue until exactly the first $ n $ cells are non-empty.
**Objective**
For each query $ x_i \in \{1, \dots, n\} $, determine the value at position $ x_i $ in the final array of length $ n $.
**Constraint**
$ 1 \leq n \leq 10^{18} $, $ 1 \leq q \leq 200000 $, $ 1 \leq x_i \leq n $.
API Response (JSON)
{
"problem": {
"name": "D. 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": "CF950D"
},
"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}^+ $, $ q \\in \\mathbb{Z}^+ $. \nLet $ A $ be an array of length $ 2n - 1 $, initially with $ a_{2i-1} = i $ for $ i = 1, \\dots, n $, and all other cells empty. ...",
"is_translate": false,
"language": "Formal"
}
]
}