有 $$$n$$$ 头牛参加编码锦标赛。奶牛 $$$i$$$ 的 Cowdeforces 评级为 $$$a_i$$$(全部不同),并且最初处于位置 $$$i$$$。锦标赛由 $$$n-1$$$ 场比赛组成,如下:
- 第一场比赛是在位置 $$$1$$$ 的奶牛和位置 $$$2$$$ 的奶牛之间进行。
- 随后,每场比赛 $$$i$$$ 均在位置 $$$i+1$$$ 的奶牛与比赛 $$$i-1$$$ 的获胜者之间进行。
- 在每场比赛中,Cowdeforces 等级较高的奶牛获胜并进入下一场比赛。
你是牛 $$$k$$$ 的主人。对你来说,赢得比赛并不重要;重要的是。相反,您希望您的牛在尽可能多的比赛中获胜。作为比赛组织者的熟人,你可以要求他们将你的牛与另一头牛交换一次,或者你可以选择什么都不做。
找出你的牛可以获得的最大胜利次数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5, 1 \le k \le n$$$) - 奶牛的数量和奶牛的索引。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 奶牛的 Cowdeforces 评级。保证 $$$a_i$$$ 是两两不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数:如果您选择最佳交换(或不执行任何操作),则牛 $$$k$$$ 可以实现的最大获胜次数。
示例
输入 #1
3 6 1 12 10 14 11 8 3 6 5 7 2 727 10 12 13 2 2 1000000000 1
输出 #1
1 2 0
注意
在第一个测试用例中,最好什么也不做。令 $$$a'$$$ 为按原始顺序排列的奶牛的 Cowdeforces 评级(您的奶牛的评级以粗体显示),然后
- 最初,$$$a' = [\mathbf{12}, 10, 14, 11, 8, 3]$$$。
- 你的牛与 Cowdeforces 评级为 $$$10$$$ 的牛进行比赛并获胜。 $$$a' = [\mathbf{12}, 14, 11, 8, 3]$$$。
- 你的牛与 Cowdeforces 评级为 $$$14$$$ 的牛比赛并输了。
在第二个测试用例中,最好将你的牛交换到位置$$$3$$$。然后,令 $$$a'$$$ 为交换后顺序中奶牛的 Cowdeforces 评级。
- 最初,$$$a' = [7, 2, \mathbf{12}, 10, 727, 13]$$$。
- Cowdeforces 评级为 $$$7$$$ 的牛与 Cowdeforces 评级为 $$$2$$$ 的牛对战并获胜。 $$$a' = [7, \mathbf{12}, 10, 727, 13]$$$。
- Cowdeforces 评级为 $$$7$$$ 的牛与你的牛对战,你的牛获胜。 $$$a' = [\mathbf{12}, 10, 727, 13]$$$。
- 你的牛与 Cowdeforces 评级为 $$$10$$$ 的牛进行比赛并获胜。 $$$a' = [\mathbf{12}, 727, 13]$$$。
- 你的牛与 Cowdeforces 评级为 $$$727$$$ 的牛比赛并输了。