Tournament Seeding

Interview

Time limit1sMemory limit1024 MB

Summary

Given 2^n player ratings and a threshold k, find the maximum number of close games in a seeded single-elimination bracket where higher ratings always win.

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

Problem

You are seeding a single-elimination tournament for a one-on-one game. The number of registered players is exactly a power of $2$ , and the tournament has exactly enough rounds to decide a winner. Each player has a unique numeric rating, and when two players meet, the player with the higher rating always wins. You want the tournament to be as exciting as possible, so it must satisfy the following properties.

The two highest rated players appear in the final, the top four appear in the semifinal, the top eight appear in the quarterfinal, and so on. The highest rated games come last.
Subject to the above, as many games as possible are "close." A game is "close" if the difference between the two players' ratings is less than or equal to a threshold.

Given the number of rounds, the threshold, and the ratings, find the maximum number of "close" games possible under these constraints.

Input

The first line contains two integers $n$ ( $1 \leq n \leq 18$ ) and $k$ ( $1 \leq k \leq 10^9$ ), where $n$ is the number of rounds and $k$ is the rating difference that makes a game "close."

Each of the next $2^n$ lines contains a single integer $r$ ( $1 \leq r \leq 10^9$ ), the rating of one player. All ratings are distinct.

Output

Print a single integer: the maximum number of "close" games possible in a tournament among these players that satisfies the constraints above.

Examples2

Example 1
Input
```
2 2
9
1
6
4
```
Expected output
```
1
```
Example 2
Input
```
2 5
9
1
6
4
```
Expected output
```
3
```