Дан массив $$$a$$$ длины $$$n$$$ и число $$$k$$$.
Подотрезком будем называть последовательность из одного и более подряд идущих элементов массива. Надо разбить массив $$$a$$$ на $$$k$$$ непересекающихся подотрезков $$$b_1, b_2, \dots, b_k$$$ так, чтобы объединение этих подотрезков было равно всему массиву и при этом $$$x$$$, равное минимальному MEX$$$(b_i)$$$, $$$i \in [1..k]$$$, было наибольшим.
MEX$$$(v)$$$ — обозначает минимальное целое неотрицательное число, которого нет в массиве $$$v$$$.
Первая строка содержит целое число $$$t$$$ $$$(1\leq t\leq 10^4)$$$ — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$, $$$k$$$ $$$(1\leq k \leq n \leq 2 \cdot 10^5)$$$ — длину массива и количество отрезков, на которые надо разбить массив.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_i$$$ $$$(0\leq a_i\leq 10^9)$$$ — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого запроса выведите одно число — такое максимальное значение $$$x$$$, что существует разбиение массива $$$a$$$ на $$$k$$$ подотрезков, при котором минимальный MEX равен $$$x$$$.
71 105 10 1 3 2 46 22 1 0 0 1 25 50 0 0 0 05 22 3 4 5 66 20 0 1 1 2 24 41 0 0 0
1 5 3 1 0 1 0
| Codeforces Round 1016 (Div. 3) |
|---|
| Закончено |
