Задана последовательность целых чисел \(a_1, a_2, \ldots, a_n\). За один ход можно выбрать любой элемент последовательности и удалить его. Все элементы справа от удаленного сдвигаются на \(1\) позицию влево, чтобы в последовательности не было пустых мест. Таким образом, за один ход длина последовательности всегда сокращается на \(1\). Индексы элементов после хода пересчитываются.
Например, пусть последовательность имеет вид \(a=[3, 2, 2, 1, 5]\). Допустим во время хода был выбран элемент \(a_3=2\). Тогда после хода последовательность будет равна \(a=[3, 2, 1, 5]\), причём теперь её \(3\)-м элементом будет считаться \(a_3=1\), а \(4\)-м будет \(a_4=5\).
Вам дана последовательность \(a_1, a_2, \ldots, a_n\) и число \(k\). Требуется найти минимальное количество ходов, которое нужно совершить, чтобы в последовательности не менее \(k\) элементов были равны своим индексам, т. е. в полученной последовательности \(b_1, b_2, \ldots, b_m\) существовало не менее \(k\) индексов \(i\) таких, что \(b_i = i\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке:
- \(-1\), если не существует искомой последовательности ходов;
- в противном случае целое число \(x\) (\(0 \le x \le n\)) — минимальное количество ходов, которое требуется, для того чтобы не менее \(k\) элементов последовательности стали равны своим индексам.
Примечание
В первом наборе входных данных последовательность изначально не удовлетворяет виду, к которому её необходимо привести, однако, удалив первый элемент последовательности, можно добиться того, что последовательность примет вид \([1, 2, 3, 4, 5, 6]\), т. е. \(6\) элементов будут равны своим индексам.
Во втором тестовом примере есть два способа достичь желаемого результата за \(2\) хода: удалить \(1\)-й и \(3\)-й элементы, при этом последовательность будет иметь вид \([1, 2, 3]\), в которой будет \(3\) равных своим индексам элемента; второй способ — удалить \(2\)-й и \(3\)-й элементы, тогда получится последовательность \([5, 2, 3]\), в которой будет \(2\) искомых элемента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 6
1 1 2 3 4 5 6
5 2
5 1 3 2 3
5 2
5 5 5 5 4
8 4
1 2 3 3 2 2 5 5
|
1
2
-1
2
|