구간을 번갈아 여는 출발식

문제

마라톤 대회의 출발식에는 참가 번호가 1번부터 N번까지인 선수들이 한 번씩 소개된다. 진행자는 번호순으로 긴 줄을 세우는 대신, 번호가 연속한 구간을 나누어 소개 순서를 정한다. 처음에는 1번부터 N번까지의 전체 구간을 깊이 0인 구간으로 놓는다. 깊이는 구간을 한 번 나눌 때마다 1씩 증가하며, 같은 깊이에 놓인 구간에는 모두 같은 규칙을 적용한다. 선수가 한 명뿐인 구간에서는 그 선수의 번호를 바로 읽는다. 선수가 두 명 이상인 구간에서는 번호가 작은 선수들로 이루어진 앞 구간과 번호가 큰 선수들로 이루어진 뒤 구간으로 나눈다. 구간에 선수가 m명 있다면 앞 구간에는 ⌈m/2⌉명, 뒤 구간에는 ⌊m/2⌋명을 넣는다. 여기서 ⌈x⌉는 x 이상인 가장 작은 정수이고, ⌊x⌋는 x 이하인 가장 큰 정수다. 따라서 인원이 홀수라면 앞 구간에 한 명이 더 들어간다. 현재 구간의 깊이가 짝수라면 앞 구간의 선수를 모두 소개한 뒤 뒤 구간의 선수를 소개한다. 깊이가 홀수라면 뒤 구간을 모두 소개한 뒤 앞 구간을 소개한다. 각 하위 구간 안의 소개 순서도 같은 규칙으로 정한다. 어느 구간을 먼저 소개하더라도 앞 구간과 뒤 구간이라는 이름은 참가 번호의 크기로 정해지며 서로 바뀌지 않는다. 운영자는 전체 소개 명단을 인쇄하지 않고, 방송 장비를 점검할 특정 순서 하나만 확인하려 한다. N과 K가 주어질 때, 전체 소개 순서에서 K번째로 불리는 선수의 참가 번호를 구하는 프로그램을 작성한다. 순서는 1번째부터 세며, 모든 선수는 정확히 한 번 불리므로 조건을 만족하는 선수는 항상 한 명이다.

입력

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

출력

전체 소개 순서에서 K번째로 불리는 선수의 참가 번호를 정수 하나로 출력한다.

7 2

4

5 4

5

1 1

1

출처: Devin.KR 자체 제작