Candale Silviu (silviu) Sofia iubește șotronul și îl joacă în fiecare zi în spatele blocului. Șotronul poate fi reprezentat ca un șir de 𝑁 pătrățele așezate în linie, numerotate de la 1 la N.
Jocul Sofiei constă în mai multe ture de joc. La începutul fiecărei ture a jocului, Sofia se află în poziția de start, aflată imediat înaintea căsuței 1, și aruncă o piatră care pică pe una dintre căsuțele șotronului. Considerăm că numărul căsuței pe care a picat piatra este i. Fetița trebuie apoi să se deplaseze până la căsuța i, efectuând unul sau mai multe salturi și să ia piatra. Cum Sofia se antrenează zilnic, a învățat deja să sară peste mai multe căsuțe, din căsuța numărul i poate sări pe căsuțele i+1, i+2 respectiv i+3, însă nu poate sări pe căsuța i+4 sau mai departe.
Regula jocului spune că pentru turele de joc care urmează, Sofia nu mai are voie să calce pe căsuța i, aceasta fiind marcată ca interzisă. Dacă piatra cade din nou pe o căsuță marcată anterior ca interzisă, jocul se încheie imediat întrucât fetița nu mai poate călca pe acea căsuță.
De exemplu, dacă Sofia se află în căsuța 2 și căsuțele 3 și 4 sunt interzise, ea poate sări peste cele două direct la căsuța 5. Dacă însă și căsuța 5 ar fi interzisă, Sofia nu ar putea sări peste toate cele trei să ajungă la căsuța 6.
Cerința
Cunoscându-se numărul N de pătrățele ale șotronului, numărul Q de aruncări pe care le-ar putea efectua fetița și indicele căsuței pe care ar ateriza piatra la fiecare aruncare, determinați care este prima aruncare la care Sofia nu mai poate recupera piatra.
Date de intrare
Fișierul de intrare sotron2.in conține pe prima linie numerele N și Q separate printr-un spațiu, având semnificația din enunț. Pe a doua linie un șir de Q numerele naturale separate prin câte un spațiu reprezentând, în ordine, poziția căsuței în care va pica piatra în cadrul fiecărei aruncări.
Date de ieșire
Fișierul de ieșire sotron2.out va conține pe prima linie un singur număr, reprezentând răspunsul determinat. Dacă Sofia poate efectua toate turele jocului respectând regulile acestuia, atunci se va afișa Q + 1.
Restricții și precizări
1 ≤ N,Q ≤ 1 000 000
Subtaskuri
- pentru 6 puncte:
N , Q ≤ 100; - pentru 17 puncte:
N , Q ≤ 500; - pentru 30 puncte:
N , Q ≤ 50 000; - pentru 47 puncte: Fără restricții suplimentare.
Exemplul 1
sotron2.in
15 10 1 14 3 12 13 4 5 7 12 10
sotron2.out
8
Explicație
La a 8-a aruncare, cea când piatra aterizează pe căsuța cu numărul 7, Sofia nu mai poate ajunge la ea pentru că nu poate sări peste căsuțele 3-5.
Exemplul 2
sotron2.in
15 10 1 14 3 12 14 4 5 7 13 10
sotron2.out
5
Explicație
La a 5-a aruncare se repetă căsuța cu numărul 14, deci Sofia nu poate ajunge la piatră.
Exemplul 3
sotron2.in
15 10 1 14 3 12 13 4 7 11 10 9
sotron2.out
11
Explicație
Sofia poate efectua toate turele, deci se afișează Q +1.