CF1967A.Permutation Counting

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

你有一些卡片。具体地，你有 $a_i$ 张写着 $i$ 的卡片 $(i\in [1,n])$ 。

现在你可以从商店购买 $k$ 张空白卡片，并且在这 $k$ 张卡片上任意填上一个 $[1,n]$ 中的整数。

定义一个序列是 $n$ 好的，且仅当它长度为 $n$ 且升序排序后是 $1$ 到 $n$ 的排列。

购买并填完 $k$ 张卡片后，你需要重新将这些卡片排序，使得你的序列中的 $n$ 好子段个数最多并求出个数。

有 $T$ 组数据。

第一行为一个正整数 $T$ ，表示数据组数。

对于每组数据：

第一行是两个非负整数 $n,k$ 。

第二行是 $n$ 个正整数，第 $i$ 个数为 $a_i$ 。

对于每一组数据，输出购买，填写并重排卡片后，卡片序列中 $n$ 好子段的最大个数并换行。

输入#1

8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8

输出#1

$1\le n\le 2\times 10^5,0\le a_i,k\le 10^{12},1\le T\le 100,1\le\sum n\le 5\times 10^5$

输入解题思路，AI测评打分。不知道怎么写?