B. Битвы коров
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
The HU - Shireg Shireg
ඞ

В турнире по программированию участвуют $$$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$$$, которого можно достичь, если сделать оптимальный обмен (или ничего не делать).

Пример
Входные данные
3
6 1
12 10 14 11 8 3
6 5
7 2 727 10 12 13
2 2
1000000000 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$$$ и проигрывает.
В общей сложности ваша корова выигрывает в $$$1$$$ матче.

Во втором наборе входных данных оптимально поменять вашу корову с коровой на позиции $$$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$$$ и проигрывает.
В общей сложности ваша корова выиграет $$$2$$$ матча.