eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Лучники

Лучники

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Соревнования лучников проходит по следующим правилам. Имеется n мишеней, расположенных в линию и пронумерованных от 1 до n включительно в соответствии с их местом на линии (самая левая мишень имеет номер 1, а самая правая мишень имеет номер n). Также есть 2*n лучников. В произвольный момент во время турнира в каждую из мишеней стреляют два лучника. Каждый тур соревнований проходит по такой процедуре:

- два лучника, стреляющие в каждую мишень, соревнуются друг с другом и определяют победителя и проигравшего. После этого все лучники перемещаются следующим образом:

- победители на мишенях с номерами от 2 до n включительно перемещаются на одну мишень левее (то есть, на мишени от 1 до n - 1 соответственно),

- проигравшие на мишенях с номерами от 2 до n включительно, так же как победитель на мишени с номером 1, остаются на тех же мишенях,

- проигравший на мишени с номером 1 перемещается на мишень с номером n.

Турнир состоит из r раундов, количество раундов не меньше, чем количество лучников (то есть r2*n). Вы – единственный лучник, который прибыл на турнир точно вовремя. Остальные 2*n - 1 лучников прибыли раньше и уже расположились в линию. Вам теперь нужно «вставиться» в линию где-то среди них. Вы знаете, что после того как вы займете свою позицию, два самых левых лучника начнут турнир на мишени с номером 1, два следующих на мишени с номером 2, и так далее. Два самых правых лучника начнут турнир на мишени с номером n.

Все 2*n лучников на турнире (включая Вас) имеют ранг, установленный в соответствии с их навыками, при этом меньший ранг соответствует более высоким навыкам. Нет двух лучников с одинаковым рангом. Также, когда бы ни соревновались два лучника, всегда победит лучник с меньшим рангом.

Зная, как сильны в стрельбе Ваши соперники, Вы хотите разместиться так, чтобы закончить турнир на мишени с наименьшим возможным номером. Если есть несколько способов сделать это, выберите тот, который начинается на мишени с наибольшим номером.

Напишите программу, которая по заданным рангам всех лучников, включая Вас, а также по расположению Ваших соперников на линии, определяет, на какой мишени вы должны начать турнир, чтобы достичь выше описанных целей.

Входные данные

Первая строка содержит два целых числа - количество мишеней n (1n200,000), равное половине количества лучников, и количество раундов турнира r (2*nr1,000,000,000), разделенные пробелом.

Последующие 2*n строк содержат ранги лучников. Первая из этих строк содержит Ваш ранг. Остальные строки содержат ранги остальных лучников по одному в строке в том порядке, в котором они расположились в линии (слева направо). Каждая из этих 2*n строк содержит одно целое число из диапазона от 1 до 2*n включительно. Ранг 1 наилучший, ранг 2*n наихудший. Никакие два лучника не имеют одинакового ранга. Известно, что 1S_k2*n, где S_k - ранг лучника с номером k.

Выходные данные

Вывести одно целое число между 1 и n включительно, являющееся номером мишени, с которой Вы начнете турнир.

Пример

Входные данные #1
4 8
7
4
2
6
5
8
1
3
Выходные данные #1
3
Источник IOI - 2009