E. Мин макс мех
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$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$$$.

Пример
Входные данные
7
1 1
0
5 1
0 1 3 2 4
6 2
2 1 0 0 1 2
5 5
0 0 0 0 0
5 2
2 3 4 5 6
6 2
0 0 1 1 2 2
4 4
1 0 0 0
Выходные данные
1
5
3
1
0
1
0