Дима — начинающий программист. В ходе работы ему регулярно приходится проделывать одну и ту же операцию: удалить из массива каждый второй элемент. В один прекрасный день ему надоели простые решения этой задачи, и он придумал следующий экстравагантный алгоритм.

Будем считать, что изначально в массиве находятся n чисел от 1 до n, причём число i располагается в ячейке c индексом 2i - 1 (нумерация элементов в массиве начинается с единицы), а остальные ячейки массива пустые. Далее, на каждом шаге Дима выбирает непустую ячейку массива с максимальным индексом, и перемещает записанное в ней число в ближайшую пустую ячейку слева от выбранной. Процесс продолжается до тех пор, пока все n чисел не окажутся в первых n ячейках массива. Например, если n = 4, содержимое массива изменяется следующим образом:

Вам предстоит написать программу, которая позволит определять, какое число окажется в ячейке под номером x (1 ≤ x ≤ n) после окончания работы алгоритма Димы.