题目描述

Gorilla and the Exam

由于“T世代”高年级学生的教师短缺，决定由一只巨大的雄性猩猩来为学生们进行考试。然而，这并不是那么简单；为了证明其能力，它需要解决以下问题。

给定一个数组 $b$ ，我们定义函数 $f(b)$ 为将数组 $b$ 变为空所需的最小操作次数：

• 选择两个整数 $l$ 和 $r$ ，满足 $l \le r$ ，并令 $x$ 为数组 $b_l, b_{l+1}, \ldots, b_r$ 中的最小值；
• 然后，删除所有满足 $l \le i \le r$ 且 $b_i = x$ 的元素，删除后的元素将被移除，剩余元素的索引重新编号。

现在给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$ 。你可以至多进行 $k$ 次修改操作，每次可以选择数组中的任意索引 $i$ （$1 \le i \le n$）和任意整数 $p$ ，将 $a_i$ 替换为 $p$ 。

帮助猩猩求出经过至多 $k$ 次替换操作后，数组 $a$ 的 $f(a)$ 可以达到的最小值。

输入格式

• 第一行是一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
• 接下来是 $t$ 组测试数据。
  • 每组数据的第一行包含两个整数 $n$ 和 $k$ （$1 \le n \le 10^5$，$0 \le k \le n$）——数组的长度和最多允许的替换次数。
  • 每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ——数组 $a$ ，其中 $1 \le a_i \le 10^9$ 。

保证所有测试数据中所有数组长度的总和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数——通过至多 $k$ 次替换操作后，数组 $a$ 的 $f(a)$ 可以达到的最小值。

说明/提示

• 在第一个测试数据中，数组 $[48843]$ 只包含一个元素，因此 $f([48843]) = 1$，只需一次操作即可删除该元素。
• 在第二个测试数据中，你可以将数组 $[2, 3, 2]$ 中的第二个元素修改为 $2$ ，使得数组变为 $[2, 2, 2]$ ，此时 $f([2, 2, 2]) = 1$ ，因为可以选择整个数组，最小值为 $2$，然后一次删除所有的 $2$ 元素。

样例

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