Вам дан массив \(a\) длины \(n\) и чётное число \(k\) (\(2 \le k \le n\)). Вам требуется разбить массив \(a\) на ровно \(k\) непустых подмассивов\(^{\dagger}\) так, чтобы каждый элемент массива \(a\) принадлежал ровно одному подмассиву.
Далее все подмассивы с чётными номерами (второй, четвёртый, \(\ldots\), \(k\)-й) склеивают в один массив \(b\). После этого в конец массива \(b\) добавляют \(0\).
Стоимостью массива \(b\) называется минимальный индекс \(i\), такой что \(b_i \neq i\). Например, стоимость массива \(b = [1, 2, 4, 5, 0]\) равна \(3\), т.к. \(b_1 = 1\), \(b_2 = 2\), \(b_3 \neq 3\). Определите минимальную стоимость массива \(b\), которую можно получить при оптимальном разбиении массива \(a\) на подмассивы.
\(^{\dagger}\)Массив \(x\) является подмассивом массива \(y\), если \(x\) может быть получен из \(y\) удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную стоимость массива \(b\), которую можно получить при оптимальном разбиении.
Примечание
В первом наборе входных данных существует всего два возможных разбиения: \([[1], [1, 1]]\) и \([[1, 1], [1]]\). В любом случае \(b_1 = 1\), а \(b_2 \ne 2\), поэтому стоимость равна \(2\).
Во втором наборе входных данных существует единственное возможное разбиение, при котором \(b = [1, 2, 3, 4, 0]\), поэтому стоимость равна \(5\) (\(b_5 = 0 \ne 5\)).
В третьем наборе входных данных подходит следующее разбиение: \([[1], [1, 1], [2], [2]]\). Тогда \(b = [1, 1, 2, 0]\), и стоимость равна \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2
1 1 1
8 8
1 1 2 2 3 3 4 4
5 4
1 1 1 2 2
5 4
1 1 1000000000 2 2
|
2
5
2
1
|