Fixing the Tournament

Interview

Time limit1sMemory limit1024 MB

Summary

Given n and your team's rank r in a bracket of 2^n single-elimination teams, find the latest round your team can reach when you choose every pairing.

Level: Medium5 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

The most common tournament format is a single elimination tournament played in rounds. To run one, the number of teams at the start must be a power of 2. For example, a tournament that starts with 16 ( $2^4$ ) teams has 8 matches in round 1, which leaves 8 winners and 8 losers. In round 2, the 8 winners are paired into 4 matches. The winners keep being paired this way until two teams remain for the final match.

In this problem, assume that:

the teams are ranked from 1 to $2^n$ for a positive integer n
the best team is ranked 1 and the worst team is ranked $2^n$ (this is called "one-based ranking")
whenever a team with a better rank (lower number) plays a team with a worse rank, the better-ranked team wins.

The pairings are not fixed. You have hacked into the tournament software, so you can pair the remaining teams in any way you want in each round. Find the highest round your favorite team can reach.

Input

A single line contains two integers: n ( $2 \le n \le 20$ ), the number of rounds in the tournament, and r ( $1 \le r \le 2^n$ ), your team's one-based ranking.

Output

Print the highest round number your team could reach, on a line by itself.

Examples3

Example 1
Input
```
4 13
```
Expected output
```
3
```
Example 2
Input
```
6 64
```
Expected output
```
1
```
Example 3
Input
```
20 2
```
Expected output
```
20
```