C. 扩充序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给定一个只包含一个数字 1 的序列 [1]。

现在,要对该序列进行 n−1 次扩充。

每次扩充时,首先要将序列本身添加到其自身的尾部,然后还要在两个序列中间插入还未使用过的最小正整数。

例如,序列 [1] 经过一次扩充后,得到序列 [1,2,1],再经过一次扩充后,得到序列 [1,2,1,3,1,2,1]。

现在,请你计算在经过 n−1 次扩充后,序列的第 k 个元素的值是多少?(元素从 1 开始编号)

输入格式

共一行,包含两个整数 n 和 k。

输出格式

输出一个整数,表示经过 n−1 次扩充后,序列的第 k 个元素的值。

样例

输入样例1:

3 2

输出样例1:

2

输入样例2:

4 8

输出样例2:

4

样例解释

对于样例 1,经过 2 次扩充,得到序列 [1,2,1,3,1,2,1],其第 2 个元素为 2。

对于样例 2,经过 3 次扩充,得到序列 [1,2,1,3,1,2,1,4,1,2,1,3,1,2,1],其第 8 个元素为 4。

数据范围与提示

对于前三个测试点, 1≤n,k≤10

对于全部测试点, 1≤n≤50, 1≤k≤2^n−1