Statement is not available in English language
B. Занавеска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алихан решил повесить новую занавеску. Занавеска держится на $$$N$$$ крючках вдоль всей гардины.

Очевидно, что если начать вешать занавеску на крючки слева направо подряд, то нагрузка будет неравномерной и гардина может свалиться.

Поэтому Алихан придерживается следующей стратегии:

  • Сначала он одновременно вешает занавеску на крючки $$$1$$$ и $$$N$$$.
  • Далее, пока есть хотя бы один неиспользованный крючок:
    • Алихан ищет непрерывный отрезок из неиспользованных крючков.
      • Среди таких отрезков Алихан выбирает отрезок наибольшей длины.
      • Среди отрезков наибольшей длины Алихан выбирает самый левый.
    • Пусть Алихан выбрал отрезок с $$$L$$$-го по $$$R$$$-й крючок, всего на нём $$$S = R - L + 1$$$ крючков. Алихан старается подвесить занавеску в центр отрезка.
      • Если количество крючков $$$S$$$ нечетное, то Алихан вешает занавеску на крючок $$$\frac{L + R}{2}$$$.
      • Иначе Алихан одновременно вешает занавеску на крючки $$$\frac{L + R - 1}{2}$$$ и $$$\frac{L + R + 1}{2}$$$.

После того, как Алихан повесил занавеску, его заинтересовало, а на каком шаге были использованы крючки под номерами $$$A_1, A_2, \dots, A_Q$$$.

Занавеска была очень большой, поэтому Алихан очень устал. Помогите Алихану и выведите для каждого интересующего Алихана крючка, на каком шаге он был использован.

Входные данные

В первой строке через пробел даны два целых числа $$$N$$$ и $$$Q$$$ $$$(1 \le N \le 10^{18}; 1 \le Q \le 10^4)$$$  — количество крючков на гардине и количество интересующих Алихана крючков.

Во второй строке через пробел записаны $$$Q$$$ различных целых чисел $$$A_1, A_2, \dots, A_Q$$$ $$$(1 \le A_i \le N)$$$  — интересующие Алихана крючки.

Выходные данные

В единственной строке через пробел выведите $$$Q$$$ чисел $$$T_i$$$  — на каком шаге был использован крючок $$$A_i$$$.

Примеры
Входные данные
10 10
1 10 2 9 3 8 4 7 5 6
Выходные данные
1 1 5 8 3 4 6 7 2 2
Входные данные
9876543210 3
3456789120 5678912340 7891234560
Выходные данные
5798205414 6764530002 3863296238
Примечание

Первый тестовый пример.

На гардине $$$N = 10$$$ крючков.

Крючки будут использованы в следующем порядке:

  1. На первом шаге вешаем на крайние крючки $$$1$$$ и $$$10$$$;
  2. На втором шаге есть один отрезок крючков $$$[2; 9]$$$, вешаем на центральные крючки $$$5 = \frac{2 + 9 - 1}{2}$$$ и $$$6 = \frac{2 + 9 + 1}{2}$$$;
  3. На третьем шаге есть два отрезка $$$[2; 4]$$$, $$$[7; 9]$$$:
    • оба имеют длину $$$3$$$, выбираем самый левый $$$[2; 4]$$$;
    • вешаем на центральный крючок $$$3 = \frac{2 + 4}{2}$$$;
  4. На четвертом шаге есть три отрезка $$$[2;2]$$$, $$$[4;4]$$$, $$$[7;9]$$$:
    • выбираем отрезок $$$[7;9]$$$, так как он имеет наибольшую длину $$$3$$$ (длина остальных $$$1$$$);
    • вешаем на центральный крючок $$$8 = \frac{7 + 9}{2}$$$;
  5. Остались крючки $$$2$$$, $$$4$$$, $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$2$$$;
  6. Остались крючки $$$4$$$, $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$4$$$;
  7. Остались крючки $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$7$$$;
  8. Остался единственный крючок $$$9$$$ — вешаем на него и заканчиваем процесс.