← 返回题目列表

Codeforces · 1951/B

B. 战牛

中文机器翻译题面 查看原题

有 $$$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$$$ 的牛比赛并输了。