题目描述

小 G 是一名图书管理员，他需要将书架上的书全部撤下。书架上共有 $n$ 本书，从左到右第 $i$ 本书的颜色编号为 $a_i$。

撤书规则如下：每次小 G 可以选择一个连续的区间 $[l, r]$，设该区间内颜色编号的最小值为 $x$，然后将该区间内所有颜色编号为 $x$ 的书撤下。被撤下的书会被移走，剩余的书保持原有顺序并向中间靠拢，重新排成一排。

在正式撤书之前，小 G 还可以进行最多 $k$ 次重新上色：选择任意一本书，将其颜色编号改为任意整数。

小 G 希望最终撤书的操作次数尽可能少。请帮他计算，在至多 $k$ 次重新上色后，最少需要多少次操作才能撤完所有书。

输入格式

第一行一个整数 $T$（$1 \le T \le 10$），表示测试点数量。

对于每个测试点：

• 第一行两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$0 \le k \le n$），分别表示书的数量和最多重新上色次数。
• 第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每本书的颜色编号。

输出格式

对于每个测试点，输出一行一个整数，表示最少需要的撤书操作次数。

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

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 10$，所有测试点中 $n$ 的总和不超过 $10^5$。

子任务

说明：对于测试点 $5,6,16,20$，数据规模均为 $n \le 10^5$，$0 \le k \le n$，$1 \le a_i \le 10^9$，无额外特殊性质；其余测试点除上表所述性质外，同样满足 $n \le 10^5$，$0 \le k \le n$，$1 \le a_i \le 10^9$。