J. 陷阱魔法 II
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

本题陷阱魔法的基本规则与题目陷阱魔法I中完全相同，不再重复说明。

猪猪学院的魔法师小猪们继续研究这种有趣的陷阱魔法。

现在，小猪们发现了这个陷阱魔法的一个漏洞：强大的大魔法师猪可以在注入魔力之前，先从陷阱中强行拉出若干只小猪。被拉出的小猪会离开队列，剩下的小猪保持原来的相对顺序形成新的队列。

作为限制，被拉出的小猪的「不能动数」之和不能超过 $$$B$$$。

如果没有剩下小猪，或者只剩下一只小猪，也认为陷阱已经被破解。

现在，小猪们想要知道：在给定初始场面和移除限制 $$$B$$$ 的情况下，通过合适的策略，最少需要注入多少点魔力，才能破解陷阱？

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：

  • 第一行两个整数 $$$n$$$ 和 $$$B$$$（$$$1\le n\le 10^5$$$ 且 $$$0 \leq B \leq \frac{n (n+1)}{2}$$$），分别表示小猪的数量和可以移除的「不能动数」总和上限。
  • 第二行 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$（$$$1 \leq a_i \leq n$$$），表示初始时刻每只小猪的「不能动数」。
  • 数据保证 $$$[a_1, a_2, \ldots, a_n]$$$ 构成一个排列。

保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^5$$$。

Output

对于每组测试用例：输出一行一个整数，表示破解陷阱所需的最小魔力值 $$$x$$$。

Example
Input
3
5 0
1 2 3 4 5
6 2
2 5 1 6 3 4
5 5
5 1 2 3 4
Output
0
3
0
Note

对于第一组测试用例，初始队列为 $$$[1,2,3,4,5]$$$，因为「不能动数」已经严格递增，因此无需移除小猪，也无需注入魔力，答案为 $$$0$$$。

对于第二组测试用例，初始队列为 $$$[2,5,1,6,3,4]$$$，可以移除的小猪的「不能动数」上限为 $$$2$$$；

最优方案是将「不能动数」为 $$$1$$$ 的小猪移除，随后队列变为 $$$[2,5,6,3,4]$$$。注入 $$$x = 3$$$ 的魔力，并依次进行操作：

  • $$$[2,5,\underline{\color{blue}{6,3,4}}] \to [2,5,\underline{\color{blue}{3,4,6}}]$$$；
  • $$$[2,\underline{\color{blue}{5,3,4}},6] \to [2,\underline{\color{blue}{3,4,5}},6]$$$；

可以证明，不存在更优方案，因此答案为 $$$3$$$。