Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Limak is a big grizzly bear who loves wrestling.
He is going to participate in a coming tournament.

There will be N = 2^{H} bears participating in the tournament.
Bears are numbered 1 through N and Limak has index 1.
Each bear has a unique value x_{i} representing his or her strength.
The tournament is divided into H stages.
In each stage bears are divided into pairs according to their indices (more info in the next paragraph).
In each pair, the two bears fight with each other and one of them wins (there are no draws).
The loser is eliminated, while the winner advances to the next stage.

In each stage, the remaining bears are sorted by their initial index.
Then, the first two bears are in one pair, next two are in the second pair, and so on.
So in the first stage there are N/2 matches: one between bear 1 and bear 2, one between bear 3 and bear 4, and so on (the last match between bear N-1 and bear N).
In the second stage, the winner of the fight between bear 1 and bear 2, will fight against the winner of the fight between bear 3 and bear 4, and so on.

Usually, when two bears fight with each other, the one with greater strength wins.
But grizzly bears aren't always honest and fair.
In each match (no matter if he fights in it or not), Limak can bribe the referee and change the winner of this match.
To avoid suspicion, he can do it only if the difference between strengths of the two bears doesn't exceed K.

For example, let's say that K = 10.
If two bears with strength 70 and 85 fight with each other, the one with strength 85 must win.
But if their strengths are 70 and 78 (or e.g. 70 and 80), Limak can bribe the referee and then the bear with strength 70 wins — but obviously Limak doesn't have to bribe the referee and then the bear with greater strength automatically wins.

What is the minimum number of times Limak has to bribe a referee, if he wants to win the tournament?
Output -1 if he can't win.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.

The first line of each test case contains two integers H and K denoting the number of stages and the maximum allowed difference of strengths between bears for Limak to bribe the referee.
Note that N = 2^{}H.

The second line of a test case contains N distinct integers: x_{1}, x_{2}, ..., x_{N}, where x_{i} denotes the strength of the i-th bear.
Limak has index 1 so his strength is x_{1}.

------ Output ------ 

For each test case, output a single line containing one integer — the minimum number of times Limak has to bribe a referee.
If he can't win the tournament, output -1 instead.

------ Constraints ------ 

$1 ≤ T ≤ 3$
$2 ≤ H ≤ 17$
$1 ≤ K ≤ 10^{9}$
$1 ≤ x_{i} ≤ 10^{9}$
$x_{i} ≠ x_{j} for i ≠ j

------ Subtasks ------ 

$Subtask #1 (25 points) 2 ≤ H ≤ 10$
$Subtask #2 (20 points) K = 10^{9}$
$Subtask #3 (55 points) Original constraints$

----- Sample Input 1 ------ 
3

2 10

70 78 67 75

3 10

18 2 19 21 33 40 26 25

2 7

4 9 8 16
----- Sample Output 1 ------ 
2

4

-1
----- explanation 1 ------ 
Test case 1. We are given H = 2 so there are N = 4 bears in the tournament.
Limak has strength 70 and he first fights against a bear with strength 78.
Limak must bribe this referee because he would lose otherwise.
In the other match of the first stage, bears with strengths 67 and 75 fight with each other.
Limak can bribe the referee of that match too, so that the bear with strength 67 advances to the next stage, where Limak beats him without bribing the referee (because Limak's strength is greater).
The answer is 2 because Limak changes results of 2 matches, and you can verify that this is the minimum.

One other optimal strategy is to allow the bear with strength 75 to win his first match.
Then Limak fights with that bear in the second stage and he can bribe the referee to win.

Test case 2. Limak must bribe at least 4 referees.
The binary tree below shows how the tournament can look like.
Each vertex with two children denotes one match (winner moves to the parent).
Red vertices denote matches where Limak bribes the referee.

Test case 3. Limak can bribe the referee to win his first match (against the bear with strength 9) but he will lose the next match against the bear with strength 16 (who must win his first match) because the difference between their strength 16 - 4 = 12 is greater than K.

Source: codechef | Difficulty: VERY_HARD
Tags: Amortized analysis

Complete search

Tree algorithms

Dynamic programming

Divide and conquer

Data structures


Solutions:
import bisect
import math

def find_possible(vec, t):
	if len(vec) == 1:
		return [(vec[0], 0)]
	p1 = find_possible(vec[:len(vec) // 2], t)
	p2 = find_possible(vec[len(vec) // 2:], t)
	i1 = 0
	i1t = 0
	i2 = 0
	i2t = 0
	min_bribe_1 = math.inf
	min_bribe_2 = math.inf
	rv = []
	while i1 < len(p1) and i2 < len(p2):
		if p1[i1][0] < p2[i2][0]:
			while i2t < len(p2) and p2[i2t][0] <= p1[i1][0] + t:
				min_bribe_2 = min(min_bribe_2, p2[i2t][1] + 1)
				i2t += 1
			min_bribe_1 = min(min_bribe_1, p1[i1][1])
			if min_bribe_2 < math.inf:
				rv.append((p1[i1][0], p1[i1][1] + min_bribe_2))
			i1 += 1
		else:
			assert p1[i1][0] > p2[i2][0]
			while i1t < len(p1) and p1[i1t][0] <= p2[i2][0] + t:
				min_bribe_1 = min(min_bribe_1, p1[i1t][1] + 1)
				i1t += 1
			min_bribe_2 = min(min_bribe_2, p2[i2][1])
			if min_bribe_1 < math.inf:
				rv.append((p2[i2][0], p2[i2][1] + min_bribe_1))
			i2 += 1
	if i1 < len(p1):
		assert min_bribe_2 == 0
		rv.extend(p1[i1:])
	if i2 < len(p2):
		assert min_bribe_1 == 0
		rv.extend(p2[i2:])
	return rv
for _ in range(int(input())):
	(__, t) = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	ans = find_possible(x, t)
	i = bisect.bisect_left(ans, (x[0] + 1, 0))
	if i == 0 or ans[i - 1][0] != x[0]:
		print(-1)
	else:
		print(ans[i - 1][1])


import bisect
import math

def find_possible(vec, t):
	if len(vec) == 1:
		return [(vec[0], 0)]
	assert len(vec) % 2 == 0
	p1 = find_possible(vec[:len(vec) // 2], t)
	p2 = find_possible(vec[len(vec) // 2:], t)
	i1 = 0
	i1t = 0
	i2 = 0
	i2t = 0
	min_bribe_1 = math.inf
	min_bribe_2 = math.inf
	rv = []
	while i1 < len(p1) and i2 < len(p2):
		if p1[i1][0] <= p2[i2][0]:
			while i2t < len(p2) and p2[i2t][0] <= p1[i1][0] + t:
				min_bribe_2 = min(min_bribe_2, p2[i2t][1] + 1)
				i2t += 1
			min_bribe_1 = min(min_bribe_1, p1[i1][1])
		if p1[i1][0] >= p2[i2][0]:
			while i1t < len(p1) and p1[i1t][0] <= p2[i2][0] + t:
				min_bribe_1 = min(min_bribe_1, p1[i1t][1] + 1)
				i1t += 1
			min_bribe_2 = min(min_bribe_2, p2[i2][1])
		if p1[i1][0] < p2[i2][0]:
			if min_bribe_2 < math.inf:
				rv.append((p1[i1][0], p1[i1][1] + min_bribe_2))
			i1 += 1
		elif p1[i1][0] > p2[i2][0]:
			if min_bribe_1 < math.inf:
				rv.append((p2[i2][0], p2[i2][1] + min_bribe_1))
			i2 += 1
		else:
			min_val = min(p1[i1][1] + min_bribe_2, p2[i2][1] + min_bribe_1)
			if min_val < math.inf:
				rv.append((p1[i1][0], min_val))
			i1 += 1
			i2 += 1
	if i1 < len(p1):
		assert min_bribe_2 == 0
		rv.extend(p1[i1:])
	if i2 < len(p2):
		assert min_bribe_1 == 0
		rv.extend(p2[i2:])
	return rv
for _ in range(int(input())):
	(h, t) = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	assert len(x) == 2 ** h
	us = x[0]
	bribe = 0
	for i in range(h):
		others = x[2 ** i:2 ** (i + 1)]
		mx = max(others)
		if mx < us:
			continue
		if mx <= us + t:
			bribe += 1
			continue
		if mx > us + t * (i + 1):
			bribe = -1
			break
		possibles = find_possible(others, t)
		p1 = bisect.bisect_left(possibles, (us, 0))
		p2 = bisect.bisect_right(possibles, (us + t, math.inf))
		if p1 > 0:
			ans1 = min((b for (__, b) in possibles[:p1]))
		else:
			ans1 = math.inf
		if p2 > p1:
			ans2 = min((b + 1 for (__, b) in possibles[p1:p2]))
		else:
			ans2 = math.inf
		ans = min(ans1, ans2)
		if ans == math.inf:
			bribe = -1
			break
		bribe += ans
	print(bribe)