Как известно, в теплую погоду многие жители крупных городов пользуются сервисами городского велопроката. Вот и Аркадий сегодня будет добираться от школы до дома, используя городские велосипеды.

Школа и дом находятся на одной прямой улице, кроме того, на той же улице есть n точек, где можно взять велосипед в прокат или сдать его. Первый велопрокат находится в точке x_1 километров вдоль улицы, второй — в точке x_2 и так далее, n-й велопрокат находится в точке x_{n}. Школа Аркадия находится в точке x_1 (то есть там же, где и первый велопрокат), а дом — в точке x_{n} (то есть там же, где и n-й велопрокат). Известно, что x_{i} < x_{i} + 1 для всех 1 ≤ i < n.

Согласно правилам пользования велопроката, Аркадий может брать велосипед в прокат только на ограниченное время, после этого он должен обязательно вернуть его в одной из точек велопроката, однако, он тут же может взять новый велосипед, и отсчет времени пойдет заново. Аркадий может брать не более одного велосипеда в прокат одновременно. Если Аркадий решает взять велосипед в какой-то точке проката, то он сдаёт тот велосипед, на котором он до него доехал, берёт ровно один новый велосипед и продолжает на нём своё движение.

За отведенное время, независимо от выбранного велосипеда, Аркадий успевает проехать не больше k километров вдоль улицы. 

Определите, сможет ли Аркадий доехать на велосипедах от школы до дома, и если да, то какое минимальное число раз ему необходимо будет взять велосипед в прокат, включая первый велосипед? Учтите, что Аркадий не намерен сегодня ходить пешком.


-----Входные данные-----

В первой строке следуют два целых числа n и k (2 ≤ n ≤ 1 000, 1 ≤ k ≤ 100 000) — количество велопрокатов и максимальное расстояние, которое Аркадий может проехать на одном велосипеде.

В следующей строке следует последовательность целых чисел x_1, x_2, ..., x_{n} (0 ≤ x_1 < x_2 < ... < x_{n} ≤ 100 000) — координаты точек, в которых находятся велопрокаты. Гарантируется, что координаты велопрокатов заданы в порядке возрастания.


-----Выходные данные-----

Если Аркадий не сможет добраться от школы до дома только на велосипедах, выведите -1. В противном случае, выведите минимальное количество велосипедов, которые Аркадию нужно взять в точках проката.


-----Примеры-----
Входные данные
4 4
3 6 8 10

Выходные данные
2

Входные данные
2 9
10 20

Выходные данные
-1

Входные данные
12 3
4 6 7 9 10 11 13 15 17 18 20 21

Выходные данные
6



-----Примечание-----

В первом примере Аркадий должен взять первый велосипед в первом велопрокате и доехать на нём до второго велопроката. Во втором велопрокате он должен взять новый велосипед, на котором он сможет добраться до четвертого велопроката, рядом с которым и находится его дом. Поэтому Аркадию нужно всего два велосипеда, чтобы добраться от школы до дома.

Во втором примере всего два велопроката, расстояние между которыми 10. Но максимальное расстояние, которое можно проехать на одном велосипеде, равно 9. Поэтому Аркадий не сможет добраться от школы до дома только на велосипедах.

Difficulty: MEDIUM

Starter code:

Solutions:
(n, k) = list(map(int, input().split()))
x = list(map(int, input().split()))
ro = list((x[i] - x[i - 1] for i in range(1, n)))
if max((x[i] - x[i - 1] for i in range(1, n))) > k:
	print(-1)
else:
	ans = 1
	r = 0
	for el in ro:
		r += el
		if r > k:
			ans += 1
			r = el
	print(ans)


(n, k) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
diff = [x[i] - x[i - 1] for i in range(1, n)]
if len(list([x for x in diff if x > k])) > 0:
	print(-1)
	return
ans = 1
cur = 0
for i in diff:
	if cur + i > k:
		ans += 1
		cur = i
	else:
		cur += i
print(ans)


(n, k) = map(int, input().split())
x = list(map(int, input().split()))
ans = 1
tmp = k
for i in range(n - 1):
	if x[i + 1] - x[i] > k:
		print(-1)
		raise SystemExit
	if tmp >= x[i + 1] - x[i]:
		tmp -= x[i + 1] - x[i]
	else:
		ans += 1
		tmp = k - x[i + 1] + x[i]
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
f = True
nn = a[0]
s = 0
nk = -1
i = 0
while i < n:
	if a[i] - nn <= k:
		nk = a[i]
		i += 1
	elif nk != -1:
		nn = nk
		s += 1
		nk = -1
	else:
		f = False
		print(-1)
		break
if f:
	print(s + 1)


(n, k) = list(map(int, input().split()))
xs = list(map(int, input().split()))
start = xs[0]
result = 1
for (i, x) in enumerate(xs):
	if x - start <= k:
		continue
	if i == 0 or xs[i] - xs[i - 1] > k:
		print(-1)
		break
	result += 1
	start = xs[i - 1]
else:
	print(result)


(n, k) = map(int, input().split())
coords = []
for i in map(int, input().split()):
	coords.append(i)
cur = 0
count = 0
while cur != len(coords) - 1 and len(coords):
	val = coords[cur] + k
	if val < coords[cur + 1]:
		print('-1')
		return
	while cur < len(coords) and val > coords[cur]:
		cur += 1
	if cur >= len(coords) or coords[cur] > val:
		cur -= 1
	count += 1
print(count)


a = input().split()
(n, k) = (int(a[0]), int(a[1]))
sharings = []
s = 0
coords = input().split()
for i in range(n):
	coord = int(coords[i])
	sharings.append(coord)
	if i != 0 and sharings[i - 1] + k < coord:
		s = 1
if s != 1:
	c = 1
	j = 1
	i = 0
	while j < n - 1:
		if sharings[i] + k < sharings[j + 1]:
			c += 1
			i = j
		j += 1
	print(c)
else:
	print(-1)


(n, k) = [int(x) for x in input().split()]
xs = [int(x) for x in input().split()]
count = 1
cur_s = 0
for i in range(n - 1):
	next_dist = xs[i + 1] - xs[i]
	if next_dist > k:
		count = -1
		break
	elif next_dist + cur_s > k:
		cur_s = next_dist
		count += 1
	else:
		cur_s += next_dist
print(count)


import sys
(n, k) = list(map(int, sys.stdin.readline().split()))
rent_points = list(map(int, sys.stdin.readline().split()))
my_list = [-1] * n
my_list[0] = 0
for i in range(1, len(my_list)):
	for j in range(0, i):
		if rent_points[i] - rent_points[j] <= k and my_list[j] != -1:
			my_list[i] = my_list[j] + 1
			break
print(my_list[n - 1])


a = list(map(int, input().split()))[1]
b = list(map(int, input().split()))
try_ = -1
c = 0
s = 0
for i in range(len(b) - 1):
	if b[i + 1] - b[i] > a:
		s = -1000000.0
while b[try_] != b[c]:
	if b[try_] - b[c] <= a:
		s += 1
		c = try_
		try_ = -1
	else:
		try_ -= 1
print(s if s > 0 else -1)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
cnt = 1
moved = 0
for i in range(1, n):
	if v[i] - v[i - 1] > k:
		print(-1)
		return
	if v[i] - v[i - 1] > k - moved:
		cnt += 1
		moved = v[i] - v[i - 1]
	else:
		moved += v[i] - v[i - 1]
print(cnt)


(n, k) = (int(i) for i in input().split())
z = [int(i) for i in input().split()]
p = z[0]
a = z[0]
res = 0
for i in z[1:]:
	if i <= a + k:
		p = i
	elif a != p:
		res += 1
		a = p
		if i > a + k:
			res = -2
			break
		p = i
	else:
		res = -2
		break
print(res + 1)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
r = 0
i = 1
while i < n:
	if a[i] - a[i - 1] > k:
		print(-1)
		return
	elif a[i] - a[i - 1] > r:
		r = k
		ans += 1
	r -= a[i] - a[i - 1]
	i += 1
print(ans)


(n, k) = [int(i) for i in input().split()]
points = [int(i) for i in input().split()]
count = 1
distance = 0
i = 1
while i < n:
	distance += points[i] - points[i - 1]
	if k < points[i] - points[i - 1]:
		count = -1
		break
	if k < distance:
		count += 1
		distance = 0
		continue
	i += 1
print(count)


(n, k) = list(map(int, input().split()))
x = [int(i) for i in input().split()]
count = 1
i = 0
f = False
while x[i] + k < x[-1]:
	if x[i] + k in x:
		i = x.index(x[i] + k)
	else:
		f = False
		max = 0
		for j in range(i, n):
			if x[j] - x[i] <= k:
				max = j
			else:
				break
		if max == i:
			f = True
			break
		else:
			i = max
	count += 1
if f:
	print(-1)
else:
	print(count)


(n, k) = list(map(int, input().split(' ')))
x = list(map(int, input().split(' ')))
m = 0
i = 0
while i != len(x) - 1:
	if x[i + 1] - x[i] == k:
		m += 1
		i += 1
	elif x[i + 1] - x[i] < k:
		for j in range(i + 1, len(x)):
			if x[j] - x[i] > k:
				break
		else:
			j += 1
		i = j - 1
		m += 1
	else:
		m = -1
		i = len(x) - 1
print(m)


(n, k) = map(int, input().split())
arr = [int(i) for i in input().split()]
i = 0
j = 1
s = 0
while i != n - 1:
	f = 0
	while j != n and arr[j] - arr[i] <= k:
		f += 1
		j += 1
	if f != 0:
		i = j - 1
		s += 1
	else:
		s = -1
		break
print(s)


(n, k) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
coun = 1
d = 0
i = 1
while i < n:
	d += p[i] - p[i - 1]
	if k < p[i] - p[i - 1]:
		coun = -1
		break
	if k < d:
		coun += 1
		d = 0
		continue
	i += 1
print(coun)


(n, k) = [int(i) for i in input().split()]
R = [int(m) for m in input().split()]
s = 0
point = 0
while point < n - 1:
	possMove = 0
	for i in range(point + 1, n):
		if R[i] - R[point] <= k:
			possMove = i
		else:
			break
	if possMove == 0:
		s = -1
		break
	else:
		s += 1
		point = possMove
print(s)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
last = A[0]
cnt = 0
f = 0
for q in range(n - 1):
	if A[q + 1] - last > k:
		if A[q] == last:
			f = 1
			break
		last = A[q]
		cnt = cnt + 1
	if A[q + 1] - last > k:
		f = 1
		break
if not f:
	print(cnt + 1)
else:
	print(-1)


(n, k) = list(map(int, input().split()))
x = [int(i) for i in input().split()]
current = x[0]
left_index = 0
right_index = 0
pe = True
count = 1
while x[left_index] + k < x[-1]:
	while x[right_index] <= x[left_index] + k:
		right_index += 1
	right_index -= 1
	count += 1
	if count > n:
		count = -1
		break
	left_index = right_index
print(count)


(n, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
i = 0
kv = 1
rest = k
while i <= n - 2:
	dist = arr[i + 1] - arr[i]
	if rest < dist:
		kv += 1
		rest = k
	if dist > k:
		kv = -1
		break
	while rest >= arr[i + 1] - arr[i]:
		rest -= arr[i + 1] - arr[i]
		i += 1
		if i == n - 1:
			break
print(kv)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
i = a[0]
home = a[-1]

def closest_point(i):
	while i not in a:
		i -= 1
	else:
		return i

def count_bikes(i, k, a):
	ans = 0
	while i != home:
		closest_poin = closest_point(i + k)
		if closest_poin == i:
			return -1
			break
		else:
			i = closest_poin
		ans += 1
	return ans
print(count_bikes(i, k, a))