2. Žer Celaskon

Po ukrutnej zime strávenej s nádchou si Zuzka uvedomila, že jej ohnutá nosná prepážka je už na nevydržanie a dá si ju operovať. Najprv však musí podstúpiť predoperačné vyšetrenie, čo znamená, že musí navštíviť doktora a stráviť tri temné doby v čakárni, kým na ňu príde rad. Čakáreň v nemocnici je v skutočnosti len dlhočizná chodba s jedným dlhým radom sedadiel, ktoré sú buď voľné, obsadené zdravým človekom alebo nejakým úbožiakom s kalným pohľadom a osoplenou vreckovkou. Keďže má Zuzka ešte stále trocha podlomenú imunitu, posledné, čo by chcela, je zase ochorieť. Preto si v čakárni chce sadnúť čo najďalej od všetkých posmrkávajúcich a odŕhajúcich ľudí. Zároveň ju však už bolia nohy z postávania v preplnenej 39-tke¹ a tento strategický výber sedadla chce spraviť čo najrýchlejšie. Pomôžete jej?

Úloha

Dostanete popis radu sedadiel v čakárni. Každé sedadlo je buď voľné, obsadené zdravým človekom, alebo obsadené chorým človekom. Vašou úlohou je nájsť to voľné sedadlo, pre ktoré je vzdialenosť od najbližšieho chorého človeka maximálna.

Formát vstupu

Sedadlá v čakárni sú zaradom očíslované kladnými celými číslami.

Na prvom riadku vstupu dostanete dve kladné celé čísla \(v, c\) označujúce počet voľných sedadiel a počet sedadiel, na ktorých sedí niekto chorý. Na druhom riadku nasleduje \(v\) čísel označujúcich pozície voľných sedadiel. Na treťom riadku je \(c\) čísel označujúcich pozície sedadiel obsadených chorými ľudmi. Na pozíciach nešpecifikovaných v predošlých dvoch riadkoch sa nachádzajú sedadlá obsadené zdravými ľuďmi.

Pre jednotlivé testovacie sady platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jediné číslo - pozíciu voľného sedadla, ktoré je najďalej od najbližšieho chorého človeka. Ak je takých sedadiel viac, vypíšte to s najnižším číslom, nech sa Zuzka toľko nenachodí.

Input:

5 4
1 11 7 6 13
3 10 4 12

Output:

7

Situáciu si môžeme zakresliť takto: -OXXO--OOX-X-O, pričom O je zdravá osoba a X chorá. Sedadlo \(1\) je od najbližšej chorej osoby (ktorá sedí na sedadle \(3\)) vzdialené \(2\), sedadlo \(6\) tiež \(2\) (v tomto prípade ide o človeka na sedadle \(4\)), sedadlo \(7\) má vzdialenosť od najbližšieho chorého človeka \(3\) (ľudia na sedadlách \(4\) a \(10\)) a sedadlá \(11\) a \(13\) majú najbližšieho chorého hneď vedľa seba.

Input:

3 3
4 7 3
5 9 1

Output:

3

Tu je situácia takáto: XO--XO-OXO. Optimálne sedadlá sú na pozíciach \(3\) a \(7\) s najbližším chorým človekom vzdialeným \(2\), no keďže sedadlo \(3\) má menšie číslo, vyberieme ho.

Input:

1 1
1
2

Output:

1

Zuzka si tu nenavyberá, musí si sadnúť hneď vedľa maróda.