spoj
Състезание
Задача
K
Наименование
ТУРНИР

Условие

K. ТУРНИР 
---
Турнир по стрелба с лък се провежда съгласно следните правила. N мишени са подредени в редица и номерирани от 1 до N, включително, според мястото им в редицата (най-лявата мишена е номер 1, а най-дясната – номер N). В турнира участват 2N стрелци. Във всеки кръг на турнира има по двама стрелци на всяка мишена. Всички стрелци са класирани по умение с число от 1 до 2N, като по-малък ранг съответства на по-доброто умение. Няма двама стрелци с еднакъв ранг. Всеки път, когато се състезават двама стрелци, печели този с по-малък ранг. 

Всеки кръг на турнира протича по следната процедура: Двамата стрелци на всяка мишена се състезават помежду си и определят победител и губещ, а след това: победителите по мишени от 2 до N, включително, се преместват на мишената отляво (т.е. на мишени от 1 до N – 1 съответно; губещите по мишени от 2 до N, включително, както и победителят по мишена 1, остават на същата мишена; губещият по мишена 1 се премества към мишена N. 

Турнирът продължава R кръга. Когато пристигнете за турнира, другите 2N – 1 стрелци са наредени в редица и вие трябва да се вмъкнете някъде сред тях. След като заемете позицията си, двамата най-леви стрелци в редицата ще започнат турнира от мишена 1, следващите два – от мишена 2 и т.н., а двамата най-десни стрелци – от мишена N. Искате да се вмъкнете по такъв начин, че да завършите турнира по мишена с възможно най-малък номер. Ако има няколко начина да направите това, предпочитате този, който започвате от мишена с възможно най-голям номер. Напишете програма, да ви помогне да изберете началната си позиция. 

Вход: Първият ред на стандартния вход съдържа броя на тестовете. Всеки тест започва с ред, който съдържа целите числа N и R, разделени с интервал. Следващият ред съдържа ранговете на стрелците. Първи в списъка е вашият ранг. Следват ранговете на останалите стрелци, в реда, по който са подредени в началото (отляво надясно). 

Изход: За всеки тестов случай програмата трябва да изведе на стандартния изход ред, cъдържащ цяло число между 1 и N, включително, което е номерът на мишената, на която трябва да започнете турнира. 

Ограничения: 1 ≤ N ≤ 200000 (броят на мишените N е половината от броя на стрелците), 2N ≤ R ≤ 1000000000, 1 ≤ Sk ≤ 2N (Sk е рангът на k-тия стрелец). 

Примерен вход:
1 
4 8 
7 
4 
2 
6 
5 
8 
1 
3 

Примерен изход:
3 

« Предходна страница Решение Въпрос