Задача №113630. Преобразование последовательности
Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые сложные задачи.
Вот и сегодня она написала на доске последовательность из \(n\) целых неотрицательных чисел чисел \(a_1, \ a_2, \dots, \ a_n\) и вызвала Колю к доске. За одно действие учительница разрешает Коле стереть любое число и на его место записать число на единицу больше. Учительница требует от Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности встречались подряд в возрастающем порядке числа от \(1\) до \(h\).
Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для некоторого \(i\) будет выполнено \(a_i \ = \ 1, a_{i \ + \ 1} \ = \ 2, \dots, \ a_{i \ + \ h \ − \ 1} \ = \ h\), или выясните, что это невозможно и учительница опять безнаказанно издевается над бедным Колей.
Первая строка входного файла содержит два натуральных числа: \(n\) и \(h\) (\(1 \le h \le n \le 200 000\)). Вторая строка содержит \(n\) чисел \(a_i\) — исходные значения элементов выписанной последовательности (\(0 \le a_i \le n\)).
В единственной строке выходного файла выведите минимальное количество действий, за которое Коля сможет выполнить задание, или −1 в случае, если выполнить его невозможно.
В первом примере Коле надо дважды увеличить на 1 третье число и один раз — четвертое. Тогда последовательность примет вид 1, 1, 2, 3, для \(i \ = \ 2\) выполнено искомое условие.
Во втором примере получить в последовательности подряд 1 и 2 невозможно.
4 3 1 1 0 2
3
3 2 1 3 2
-1