Amr 购买了一款新视频游戏“猜猜你的出路!”。游戏的目标是找到迷宫的出口,该出口看起来像高度为 h 的完美二叉树。玩家最初站在树的根部,树的出口位于某个叶节点。
让我们从左到右索引 1 到 2h 的所有叶节点。出口位于某个节点 n,其中 1 ≤ n ≤ 2h,玩家不知道出口在哪里,所以他必须猜测出路!
Amr遵循简单的算法来选择路径。让我们考虑无限命令字符串“LRLRLRLRL...”(由交替的字符“L”和“R”组成)。 Amr 使用以下规则顺序执行字符串的字符:
- 字符“L”表示“转到当前节点的左子节点”;
- 字符“R”表示“转到当前节点的右子节点”;
- 如果目标节点已经被访问过,Amr 跳过当前命令,否则移动到目标节点;
- 如果Amr连续跳过两个命令,他会在执行下一个命令之前返回当前节点的父节点;
- 如果到达不是出口的叶子节点,则返回当前节点的父节点;
- 如果他到达出口,游戏就结束。
现在 Amr 想知道,如果他遵循这个算法,在到达出口之前他将访问多少个节点?
输入
输入由两个整数 h、n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2h) 组成。
输出
按照此算法输出一个整数,表示 Amr 在到达出口之前将要访问的节点数(不包括出口节点)。
示例
输入 #1
1 2
输出 #1
2
输入 #2
2 3
输出 #2
5
输入 #3
3 6
输出 #3
10
输入#4
10 1024
输出#4
2046
注意
高度为 h 的完美二叉树是由 h + 1 层组成的二叉树。级别 0 由称为根的单个节点组成,级别 h 由称为叶的 2h 个节点组成。每个不是叶子的节点都恰好有两个子节点,左节点和右节点。
下图是示例测试编号 3。节点按照访问顺序进行标记。