311216: CF1951B. Battle Cows
Description
There are $n$ cows participating in a coding tournament. Cow $i$ has a Cowdeforces rating of $a_i$ (all distinct), and is initially in position $i$. The tournament consists of $n-1$ matches as follows:
- The first match is between the cow in position $1$ and the cow in position $2$.
- Subsequently, each match $i$ is between the cow in position $i+1$ and the winner of match $i-1$.
- In each match, the cow with the higher Cowdeforces rating wins and proceeds to the next match.
You are the owner of cow $k$. For you, winning the tournament is not important; rather, you want your cow to win in as many matches as possible. As an acquaintance of the tournament organizers, you can ask them to swap the position of your cow with another cow only once, or you can choose to do nothing.
Find the maximum number of wins your cow can achieve.
InputEach test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5, 1 \le k \le n$) — the number of cows and your cow's index.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the Cowdeforces rating of the cows. It is guaranteed that $a_i$'s are pairwise different.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, print one integer: the maximum number of wins cow $k$ can achieve if you choose to swap (or do nothing) optimally.
ExampleInput3 6 1 12 10 14 11 8 3 6 5 7 2 727 10 12 13 2 2 1000000000 1Output
1 2 0Note
In the first test case, it is optimal to do nothing. Let $a'$ be the Cowdeforces rating of the cows in the original order (with your cow's rating bolded), then
- Initially, $a' = [\mathbf{12}, 10, 14, 11, 8, 3]$.
- Your cow plays against the cow with Cowdeforces rating $10$ and wins. $a' = [\mathbf{12}, 14, 11, 8, 3]$.
- Your cow plays against the cow with Cowdeforces rating $14$ and loses.
In the second test case, it is optimal to swap your cow to position $3$. Then, let $a'$ be the Cowdeforces rating of the cows in the order after the swap.
- Initially, $a' = [7, 2, \mathbf{12}, 10, 727, 13]$.
- The cow with Cowdeforces rating $7$ plays against the cow with Cowdeforces rating $2$ and wins. $a' = [7, \mathbf{12}, 10, 727, 13]$.
- The cow with Cowdeforces rating $7$ plays against your cow, and your cow wins. $a' = [\mathbf{12}, 10, 727, 13]$.
- Your cow plays against the cow with Cowdeforces rating $10$ and wins. $a' = [\mathbf{12}, 727, 13]$.
- Your cow plays against the cow with Cowdeforces rating $727$ and loses.
Output
有 n 头牛参加编程比赛，每头牛有一个不同的 Cowdeforces 评分 \(a_i\)，初始时位于位置 i。比赛由 n-1 轮对决组成：
- 第一轮是位置 1 和位置 2 的牛对决。
- 之后，每一轮对决 i 是位置 i+1 的牛与第 i-1 轮的胜者对决。
- 在每一轮对决中，评分较高的牛获胜并进入下一轮。
你是编号为 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 头牛参加编程比赛，每头牛有一个不同的 Cowdeforces 评分 \(a_i\)，初始时位于位置 i。比赛由 n-1 轮对决组成： - 第一轮是位置 1 和位置 2 的牛对决。 - 之后，每一轮对决 i 是位置 i+1 的牛与第 i-1 轮的胜者对决。 - 在每一轮对决中，评分较高的牛获胜并进入下一轮。 你是编号为 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\) 互不相同。 输出： - 对于每个测试用例，输出一行，包含一个整数，表示如果最优地选择交换或不交换，你的牛能获得的最大胜利次数。