B. Горилла и зачет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Из-за нехватки преподавателей в самой высокой параллели «Т-поколения» было принято решение поставить огромного самца гориллы принимать зачет у школьников. Но не все так просто, для того чтобы доказать свою компетентность, ему нужно решить следующую задачу.

Для массива $$$b$$$ определим функцию $$$f(b)$$$ как минимальное количество следующих операций, чтобы сделать массив $$$b$$$ пустым:

  • взять два целых числа $$$l$$$ и $$$r$$$, такие что $$$l \le r$$$, пусть $$$\min(b_l, b_{l+1}, \ldots, b_r)$$$ равен $$$x$$$, затем
  • удалить из массива все такие $$$b_i$$$, что $$$l \le i \le r$$$ и $$$b_i = x$$$, удаленные элементы удаляются, индексы перенумеруются

Дан массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$. Вы можете не более $$$k$$$ раз выбрать любой индекс $$$i$$$ ($$$1 \le i \le n$$$) и произвольное число $$$p$$$, и заменить $$$a_i$$$ на $$$p$$$.

Помогите горилле и определите, какое минимальное значение $$$f(a)$$$ можно получить после таких замен.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le n$$$) — длина массива $$$a$$$ и максимальное число изменений соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сам массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите одно целое число — минимальное значение $$$f(a)$$$.

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

В первом наборе входных данных $$$f([48\,843]) = 1$$$, так как массив состоит из одного числа, а значит, можно его удалить за одну операцию.

Во втором наборе входных данных можно изменить второе число на $$$2$$$, получив массив $$$[2, 2, 2]$$$, $$$f([2, 2, 2]) = 1$$$, так как можно взять в качестве подотрезка весь массив, минимум на нем равен $$$2$$$, поэтому мы удалим все числа $$$2$$$ из массива, и массив станет пустым.