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

Школа и дом находятся на одной прямой улице, кроме того, на той же улице есть 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: interview

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
    else:
        if 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):
    #next_coord = coords.pop(0)
    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)




#   TaskA

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])


#!/usr/bin/env python3

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 = -10e5

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:
    #print("get at", v[i-1])
    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];
#print(last);
#last = 0;
cnt = 0;
f = 0;
for q in range(n - 1):
    #print(A[q + 1], last, k);
    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))