Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Преобразование последовательности

Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые
сложные задачи.
Вот и сегодня она написала на доске последовательность из n целых неотрицательных чисел
чисел a1, a2, . . . , an и вызвала Колю к доске. За одно действие учительница разрешает Коле
стереть любое число и на его место записать число на единицу больше. Учительница требует от
Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности
встречались подряд в возрастающем порядке числа от 1 до h.
Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для
некоторого i будет выполнено ai = 1, ai+1 = 2, . . . , ai+h−1 = h, или выясните, что это невозможно и
учительница опять безнаказанно издевается над бедным Колей.

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

Примеры
Ввод
4 3
1 1 0 2
Вывод
3

Ввод
3 2
1 3 2
Вывод
-1

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


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: