Задача D. Лара Крофт и подвесной мост ≡

Условие

Расхитительница гробниц Лара Крофт стоит на левом краю ущелья. Она хочет перебраться на правую сторону чтобы исследовать древний храм. Для этого ей нужно без остановок пробежать вперёд по подвесному мосту длиной N досок.

В ущелье бушует сильный ветер, поэтому каждую секунду где-то может упасть одна или несколько досок, либо не упасть ни одной. Каждую секунду Лара должна прыгнуть вперёд на любое количество досок от 1 до K. Если доска, на которую собирается прыгнуть Лара, обвалится в ту же секунду, то приключение героини окончено.

Оракул подсказал Ларе N чисел x_i — номера секунд, в который обвалится i-ая доска подвесного моста. В нулевую секунду Лара стоит на левом краю ущелья.

Необходимо определить, сможет ли Лара перебраться на правую сторону ущелья и если да, то за сколько секунд.

Формат входного файла

Первая строка входного файла содержится целые числа N и K.

Вторая строка содержит N целых чисел x_i.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальное количество секунд, за которые Лара преодолеет мост и окажется на правой стороне ущелья.

Если Лара не сможет добраться до другой стороны ущелья, выведите  − 1.

Ограничения

0 ≤ K ≤ 100

1 ≤ N ≤ 10⁵

0 ≤ x_i ≤ 2 ⋅ 10⁵

Примеры тестов

6 1
1 1 4 5 8 0

-1

10 2
4 2 2 5 10 5 4 9 0 10

6