由于“T一代”高年级师资短缺,决定用一只巨大的雄性大猩猩为学生进行考试。然而,事情并没有那么简单;为了证明他的能力,他需要解决以下问题。
对于数组 $$$b$$$,我们将函数 $$$f(b)$$$ 定义为使数组 $$$b$$$ 为空所需的以下操作的最小数量:
- 取两个整数$$$l$$$和$$$r$$$,使得$$$l \le r$$$,并令$$$x$$$为$$$\min(b_l, b_{l+1}, \ldots, b_r)$$$;那么
- 从数组中删除所有这样的 $$$b_i$$$ , $$$l \le i \le r$$$ 和 $$$b_i = x$$$ ,删除的元素被删除,索引被重新枚举。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$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)$$$ 的最小可能值。
示例
输入 #1
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 1 2 5 2 1
注意
在第一组输入数据中,$$$f([48\,843]) = 1$$$,因为该数组由单个数字组成,因此可以在一次操作中将其删除。
在第二组输入数据中,你可以将第二个数字改为$$$2$$$,得到数组$$$[2, 2, 2]$$$,其中$$$f([2, 2, 2]) = 1$$$,因为你可以将整个数组作为子数组,所以它的最小值是$$$2$$$,所以我们将删除所有$$$2$$$数组,数组将变为空。