Задача №113907. Чехарда в массиве
Дима — начинающий программист. В ходе работы ему регулярно приходится проделывать одну и ту же операцию: удалить из массива каждый второй элемент. В один прекрасный день ему надоели простые решения этой задачи, и он придумал следующий экстравагантный алгоритм.
Будем считать, что изначально в массиве находятся n чисел от 1 до n , причём число i располагается в ячейке c индексом 2 i - 1 (нумерация элементов в массиве начинается с единицы), а остальные ячейки массива пустые. Далее, на каждом шаге Дима выбирает непустую ячейку массива с максимальным индексом, и перемещает записанное в ней число в ближайшую пустую ячейку слева от выбранной. Процесс продолжается до тех пор, пока все n чисел не окажутся в первых n ячейках массива. Например, если n = 4 , содержимое массива изменяется следующим образом:
Вам предстоит написать программу, которая позволит определять, какое число окажется в ячейке под номером x ( 1 ≤ x ≤ n ) после окончания работы алгоритма Димы.
В первой строке вводятся целые числа n и q ( 1 ≤ n ≤ 10 18 , 1 ≤ q ≤ 200 000 ) — число элементов в массиве и количество запросов, на которые необходимо дать ответ. В каждой из последующих q строк вводится целое число x i ( 1 ≤ x i ≤ n ) — номер ячейки, для которой необходимо определить содержимое после окончания работы алгоритма.
Для каждого из q запросов выведите одно целое число — значение, которое будет содержать указанная ячейка массива после окончания работы алгоритма Димы.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
4 3 2 3 4
3 2 4