Лучники
Лучники
Соревнования лучников проходит по следующим правилам. Имеется n мишеней, расположенных в линию и пронумерованных от 1 до n включительно в соответствии с их местом на линии (самая левая мишень имеет номер 1, а самая правая мишень имеет номер n). Также есть 2*n лучников. В произвольный момент во время турнира в каждую из мишеней стреляют два лучника. Каждый тур соревнований проходит по такой процедуре:
- два лучника, стреляющие в каждую мишень, соревнуются друг с другом и определяют победителя и проигравшего. После этого все лучники перемещаются следующим образом:
- победители на мишенях с номерами от 2 до n включительно перемещаются на одну мишень левее (то есть, на мишени от 1 до n - 1 соответственно),
- проигравшие на мишенях с номерами от 2 до n включительно, так же как победитель на мишени с номером 1, остаются на тех же мишенях,
- проигравший на мишени с номером 1 перемещается на мишень с номером n.
Турнир состоит из r раундов, количество раундов не меньше, чем количество лучников (то есть r ≥ 2*n). Вы – единственный лучник, который прибыл на турнир точно вовремя. Остальные 2*n - 1 лучников прибыли раньше и уже расположились в линию. Вам теперь нужно «вставиться» в линию где-то среди них. Вы знаете, что после того как вы займете свою позицию, два самых левых лучника начнут турнир на мишени с номером 1, два следующих на мишени с номером 2, и так далее. Два самых правых лучника начнут турнир на мишени с номером n.
Все 2*n лучников на турнире (включая Вас) имеют ранг, установленный в соответствии с их навыками, при этом меньший ранг соответствует более высоким навыкам. Нет двух лучников с одинаковым рангом. Также, когда бы ни соревновались два лучника, всегда победит лучник с меньшим рангом.
Зная, как сильны в стрельбе Ваши соперники, Вы хотите разместиться так, чтобы закончить турнир на мишени с наименьшим возможным номером. Если есть несколько способов сделать это, выберите тот, который начинается на мишени с наибольшим номером.
Напишите программу, которая по заданным рангам всех лучников, включая Вас, а также по расположению Ваших соперников на линии, определяет, на какой мишени вы должны начать турнир, чтобы достичь выше описанных целей.
Входные данные
Первая строка содержит два целых числа - количество мишеней n (1 ≤ n ≤ 200,000), равное половине количества лучников, и количество раундов турнира r (2*n ≤ r ≤ 1,000,000,000), разделенные пробелом.
Последующие 2*n строк содержат ранги лучников. Первая из этих строк содержит Ваш ранг. Остальные строки содержат ранги остальных лучников по одному в строке в том порядке, в котором они расположились в линии (слева направо). Каждая из этих 2*n строк содержит одно целое число из диапазона от 1 до 2*n включительно. Ранг 1 наилучший, ранг 2*n наихудший. Никакие два лучника не имеют одинакового ранга. Известно, что 1 ≤ S_k ≤ 2*n, где S_k - ранг лучника с номером k.
Выходные данные
Вывести одно целое число между 1 и n включительно, являющееся номером мишени, с которой Вы начнете турнир.
Пример
4 8 7 4 2 6 5 8 1 3
3