Alex are o gramada de n bucati de lemn, de dimensiuni diferite, date in ordine crescatoare. Prima bucata are intotdeauna dimensiunea 1 si este chibritul cu care Alex aprinde focul, la momentul t=1.
O bucata de lemn de dimensiune d, aprinsa la momentul t, aprinde la momentul t+1 toate bucatile neaprinse de dimensiune cel mult 2*d.
Care este primul moment de timp la care toate bucatile de lemn sunt aprinse?
- Date de intrare
- Pe prima linie se citeste numarul intreg n. Pe a doua linie se citesc n numere intregi, dimensiunile bucatilor de lemn, date in ordine crescatoare (primul numar este intotdeauna 1).
- Date de iesire
- Se afiseaza un singur numar intreg: primul moment de timp la care toate bucatile de lemn sunt aprinse.
- Restrictii
- 1 <= n <= 1000 dimensiunile sunt date in ordine crescatoare (nu neaparat strict) prima dimensiune este intotdeauna 1 se garanteaza ca toate bucatile pot fi aprinse 1 <= dimensiune <= 10^9
Exemple
Exemplul 1
Intrare
21 1 2 2 2 3 5 5 5 7 13 14 15 15 25 35 50 50 51 78 99 100
Iesire
9
Exemplul 2
Intrare
1 1
Iesire
1