0398. Преобразование последовательности

Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые сложные задачи.

Вот и сегодня она написала на доске последовательность из n целых неотрицательных чисел чисел a₁, a₂, …, a_n и вызвала Колю к доске. За одно действие учительница разрешает Коле стереть любое число и на его место записать число на единицу больше. Учительница требует от Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности встречались подряд в возрастающем порядке числа от 1 до h.

Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для некоторого i будет выполнено a_i=1, a_i+1=2, …, a_i+h-1=h, или выясните, что это невозможно и учительница опять безнаказанно издевается над бедным Колей.

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

Первая строка входного файла содержит два натуральных числа: n и h (1 ≤ h ≤ n ≤ 200,000). Вторая строка содержит n чисел a_i – исходные значения элементов выписанной последовательности (0 ≤ a_i ≤ n).

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

В единственной строке выходного файла выведите минимальное количество действий, за которое Коля сможет выполнить задание, или -1 в случае, если выполнить его невозможно.

Пример:

В первом примере Коле надо дважды увеличить на 1 третье число и один раз – четвертое. Тогда последовательность примет вид 1, 1, 2, 3, для i=2 выполнено искомое условие.

Во втором примере получить в последовательности подряд 1 и 2 невозможно.

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати