시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые сложные задачи.
Вот и сегодня она написала на доске последовательность из $n$ целых неотрицательных чисел чисел $a_1, a_2, \ldots, 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$ в случае, если выполнить его невозможно.
4 3 1 1 0 2
3
3 2 1 3 2
-1
В первом примере Коле надо дважды увеличить на 1 третье число и один раз --- четвертое. Тогда последовательность примет вид 1, 1, 2, 3, для $i=2$ выполнено искомое условие.
Во втором примере получить в последовательности подряд 1 и 2 невозможно.