Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: pomidorai.in

Rezultatų failas: pomidorai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Pomidorai

Žinomas įdomus faktas: tarp neprinokusių pomidorų padėjus keletas raudonų pomidorų, aplink juos esantys žali pomidorai ims nokti greičiau.

Vienoje eilėje sudėta n pomidorų. Laikykime, kad jie sunumeruoti nuo 1 iki n. k iš šių pomidorų yra raudoni, jų numeriai yra m1 , m2 , ..., mk. Per vieną dieną prinoksta abu kiekvieno raudono pomidoro kaimynai (suprantama, kraštinis pomidoras turi tik vieną kaimyną).

pomidoras1

pomidoras2

pomidoras3

Parašykite algoritmą, kuris suskaičiuotų, per kiek dienų prinoks visi pomidorai.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas skaičiai n ir k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n). Kitose k eilučių išvardinti raudonų pomidorų numeriai m1 , m2 , ..., mk, didėjimo tvarka.

Rezultatai

Rezultatą – dienų skaičių – jūsų programa turi išvesti pirmoje rezultatų failo eilutėje.

Pavyzdžiai

Pradiniai duomenys Rezultatai
19 3 
2 
13 
15
5