Задача №1968.
Соревнования лучников проходит по следующим правилам. Есть \(N\) мишеней, расположенных в линию и пронумерованных от \(1\) до \(N\) включительно в соответствии с их местом на линии (самая левая мишень имеет номер 1, а самая правая мишень имеет
номер \(N\)). Также есть \(2*N\) лучников. В произвольный момент во время турнира в каждую из мишеней стреляют два лучника. Каждый тур соревнований проходит по такой процедуре:
- два лучника, стреляющие в каждую мишень, соревнуются друг с другом и определяют победителя и проигравшего. После этого все лучники перемещаются следующим образом:
- победители на мишенях с номерами от \(2\) до \(N\) включительно перемещаются на одну мишень левее (то есть, на мишени от \(1\) до \(N - 1\) соответственно),
- проигравшие на мишенях с номерами от \(2\) до \(N\) включительно, так же как победитель на мишени с номером \(1\), остаются на тех же мишенях,
- проигравший на мишени с номером \(1\) перемещается на мишень с номером \(N\).
Турнир состоит из \(R\) туров, количество туров не меньше, чем количество лучников (то есть \(R \ge 2*N)\).
Вы – единственный лучник, который прибыл на турнир точно вовремя. Остальные \(2*N - 1\) лучников прибыли раньше и уже расположились в линию. Вам теперь нужно «вставиться» в линию где-то среди них. Вы знаете, что после того как вы займете свою позицию, два самых левых лучника начнут турнир на мишени с номером \(1\), два следующих на мишени с номером \(2\), и так далее. Два самых правых лучника начнут турнир на мишени с номером \(N\).
Все \(2*N\) лучников на турнире (включая вас) имеют ранг, установленный в соответствии с их навыками, при этом меньший ранг соответствует более высоким навыкам. Нет двух лучников одинаковым рангом. Также, когда бы ни соревновались два лучника, всегда победит лучник с меньшим рангом.
Зная, как сильны в стрельбе ваши соперники, вы хотите разместиться так, чтобы закончить турнир на мишени с наименьшим возможным номером. Если есть несколько способов сделать это, выберите тот, который начинается на мишени с наибольшим номером.
Напишите программу, которая по заданным рангам всех лучников, включая вас, а также по расположению ваших соперников на линии, определяет, на какой мишени вы должны начать турнир, чтобы достичь описанных выше целей.
Ваша программа должна читать со стандартного потока ввода такие данные:
- Первая строка содержит целые числа \(N\) и \(R\), разделенные пробелом. \(1 \le N \le 200\,000\) Количество мишеней (также равно половине количества лучников). \(2*N \le R \le 1\,000\,000\,000\) Количество туров турнира.
- Последующие \(2*N\) строк содержат ранги лучников. \(1 \le S_k \le 2*N\) Ранг лучника с номером k. Первая из этих строк содержит ваш ранг. Остальные строки содержат ранги остальных лучников по одному в строке в том порядке, в котором они расположились в линии (слева направо). Каждая из этих \(2*N\) строк содержит одно целое число из диапазона от \(1\) до \(2*N\) включительно. Ранг \(1\) - наилучший, ранг \(2*N\) - наихудший. Никакие два лучника не имеют одинакового ранга.
Ваша программа должна записать в стандартный поток вывода одну строку, в которой будет содержаться одно целое число между \(1\) и \(N\) включительно, являющееся номером мишени, на которой вы начнете турнир.
В тесте из условия вы второй наихудший лучник. Если вы начнете на мишени с номером 1, то вы попадете на мишень с номером 4 и останетесь там до конца. Если вы начнете на мишени с номером 2 или 4, вы просто останетесь там до конца турнира. Если вы начнете на мишени с номером 3, то победите наихудшего лучника, переместитесь на мишень с номером 2 и там останетесь.
В тесте (ниже) вы второй наилучший лучник. Наилучший лучник уже расположен на мишени с номером 1, и останется там до окончания турнира. Таким образом, вне зависимости от того, где вы начнете турнир, вы будете всегда передвигаться со своей мишени,
проходя через все мишени с номерами от 4 до 1 снова и снова. Для того чтобы окончить турнир на мишени с номером 1 после девяти переходов, вы должны начать на мишени с номером 2.
| Пример ввода | Пример вывода |
|---|---|
| 4 9 2 1 5 8 3 4 7 6 |
2 |
Для набора тестов общей стоимостью \(60\) баллов \(N\) не будет превышать \(5\,000\).
Также, для некоторых из этих тестов, суммарной стоимостью \(20\) баллов, \(N\) не будет превышать \(200\).
4 8 7 4 2 6 5 8 1 3
3