Po maturite riešil mladý Vašino zapeklitý problém - raz sa prázdniny skončia a bude treba ísť do školy. Teraz bol problém ešte zložitejší, lebo si vyberal, kam pôjde študovať. Situácia závažná, nakoniec sa ale rozhodol, že MatFyz je najlepšie miesto na študovanie informatiky na svete.
Hodil si mincou, či bude bývať na internáte alebo si pohľadá nejaký podnájom. Keďže padla hlava, bude musieť byť ďalší rok sociálnejší a zabývať sa na internáte.
Keď Vašino pricestoval na intrák, najviac ho zaujal výťah vo výškovej budove. Všimol si, že niektoré poschodia sú vo výťahu špeciálne vyznačené. Hneď mu bolo jasné, že ide o nejaké mysteriózne poschodia. Keďže Vašino je len zmätený prvák, radšej by sa im vyhol. Zároveň má ale Vašino rád vozenie sa výťahom a tak chce zistiť, koľko najviac si vie užívať bezstarostnú jazdu, bez prechádzania cez takéto desivé poschodia. Inak povedané, koľko najviac poschodí po sebe sa vie viezť tak, aby neprešiel ani jedným mysterióznym poschodím.
Úloha
Výťah vie klesnúť najviac na poschodie číslo \(z\) (ako začiatočné) a ide hore až po poschodie číslo \(k\) (ako konečné). Mysteriózne poschodia sú označené číslami z množiny celých čisel na tomto intervale.
Vašou úlohou je určiť, aký dlhý je najdlhší úsek po ceste zo \(z\) do \(k\) je taký, že na ňom neprejdeme cez žiadne mysteriózne poschodia. (Dĺžka úseku je počítaná ako počet nemysterióznych poschodí, ktoré cesta obsahuje. Teda sa tam počítajú aj začiatočné a konečné poschodie.)
Formát vstupu
V prvom riadku sú dve hodnoty \(z\) a \(k\) oddelené medzerou (\(1 \leq z < k \leq 10^{12}\)) - spolu predstavujú interval, na ktorom premáva výťah.
V druhom riadku je práve jedno číslo \(p\), určujúce počet poschodí, ktoré sú mysteriózne.
V treťom, poslednom riadku, je \(p\) medzerou oddelených čísel, reprezentujúce mysteriózne poschodia, cez ktoré nechceme prejsť výťahom, ani tam nastúpiť či vystúpiť.
Hodnotenie
Premenná \(n\) reprezentuje celkový počet poschodí, teda \(n = k-z+1\), cez ktoré premáva výťah. Premenná \(p\) reprezentuje počet mysterióznych poschodí, ktorým sa treba vyvarovať. Platí, že ľubovolné tajné poschodie nie je menšie ako \(z\) ani väčšie ako \(k\). V nasledujúcej tabuľke uvádzame horné obmedzenia pre \(n\) a \(p\) v 4 sadách vstupov - za každú úspešne vyriešenú sadu vám testovač udelí 2 body.
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(20\) | \(1\,000\) | \(10^{5}\) | \(10^{12}\) |
\(0 \leq p \leq\) | \(20\) | \(1\,000\) | \(10^5\) | \(10^6\) |
Formát výstupu
Vypíšte jeden riadok a v ňom jedno celé číslo - dĺžka najdlhšieho úseku cesty výťahom bez prechodu cez nejaké mysteriózne poschodie.
Príklady
Input:
2 11
2
4 9
Output:
4
Najdlhšie sa budeme viesť 4 poschodia a to od piateho po ôsme (vrátane).
Input:
1 4
1
1
Output:
3
Nastupujeme na druhom a ideme až na štvrté - dokopy tri poschodia.
Input:
40 533
5
95 71 533 49 233
Output:
299
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.