가장 먼 빈방

문제

일렬로 늘어선 객실 1번부터 N번까지가 있는 호텔이 있다. 처음에는 모든 객실이 비어 있고, 손님 N명이 1번 손님부터 N번 손님까지 차례대로 도착한다. 방 배정 규칙은 다음과 같다. 1번 손님은 1번 객실에 든다. N이 2 이상이면 2번 손님은 N번 객실에 든다. 그 이후의 손님은 이미 찬 객실로 둘러싸인 빈 구간 중 하나를 골라 그 가운데 객실에 든다. 구체적으로, 찬 객실 a와 b(a < b)가 인접한 찬 객실이고 그 사이에 빈 객실이 있으면 b - a ≥ 2이며, 이 구간에서 손님이 들 객실은 a + floor((b - a) / 2)번이다. 이때 이 객실에서 가장 가까운 찬 객실까지의 거리는 floor((b - a) / 2)이며, 이 값을 구간의 거리라고 한다. 손님은 거리가 가장 큰 구간을 고르고, 거리가 같은 구간이 여럿이면 들어갈 객실 번호가 가장 작은 구간을 고른다. 한 구간에 들면 그 구간은 (a, 객실)과 (객실, b)의 두 구간으로 나뉜다. 이렇게 모든 손님이 객실에 들 때까지 반복한다. Q개의 질문에 답하시오. 각 질문은 정수 k이며, k번 손님이 든 객실의 번호를 구하는 것이다.

입력

첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 Q개의 정수 k가 공백으로 구분되어 주어진다. (1 ≤ k ≤ N)

출력

각 질문에 대한 객실 번호를 입력 순서대로 한 줄에 하나씩 출력한다.

6 3
3 5 6

3
4
5

1 1
1

1

10 4
10 4 1 7

9
3
1
4

출처: Devin.KR 자체 제작