가운데부터 켜지는 좌석등

문제

작은 영화관은 상영 전 좌석등을 하나씩 켜면서 조명 장치를 점검한다. 점검할 좌석은 한 줄에 놓여 있으며, 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 모든 좌석등은 처음에 꺼져 있다. 운영자는 좌석을 왼쪽부터 차례대로 점검하는 대신, 구간을 나누는 재귀적인 절차를 사용한다. 좌석 번호 L부터 R까지의 구간을 점검할 때는 먼저 가운데 좌석 M의 등을 켠다. 여기서 M은 (L+R)을 2로 나눈 몫이다. 따라서 구간에 좌석이 짝수 개 있으면 가운데의 두 좌석 중 번호가 작은 좌석을 선택한다. 그다음 L번부터 M-1번까지의 왼쪽 구간을 같은 절차로 모두 점검하고, 왼쪽 점검이 끝난 뒤에 M+1번부터 R번까지의 오른쪽 구간을 같은 절차로 모두 점검한다. L이 R보다 크면 그 구간에는 좌석이 없으므로 아무 일도 하지 않는다. 전체 점검은 1번부터 N번까지의 구간에서 시작한다. 가운데 좌석의 등을 켠 뒤에는 왼쪽 구간 전체가 오른쪽 구간보다 먼저 처리된다는 점에 주의해야 한다. 각 좌석등은 정확히 한 번 켜지며, 등을 켜는 동작 하나를 한 순서로 센다. 구간을 나누거나 빈 구간을 확인하는 일은 순서에 포함하지 않는다. 점검 담당자는 기록지에 K번째로 켜지는 좌석의 번호 하나만 적으려고 한다. N과 K가 주어질 때 그 좌석 번호를 구하는 프로그램을 작성한다. K는 1 이상 N 이하이므로 해당하는 좌석은 항상 존재하며, 출력할 답도 하나로 결정된다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000
1 ≤ K ≤ N

출력

K번째로 등이 켜지는 좌석의 번호를 정수 하나로 출력한다.

7 5

6

8 8

8

1 1

1

출처: Devin.KR 자체 제작