Spilja

U špilji pored Mirkovog sela navodno su još prije nekoliko tisuća godina živjeli njegovi preci. Mirko je zaključio da je jedino on sam sposoban pronaći ostatke te drevne civilizacije i počeo je s pripremama za istraživanje. Tako je on kupio nove hlače, čizme, lopatu i čekić. Netom prije početka istraživanja, zaključio je da u pećini ipak nema struje i da mora kupiti nekakve lampe. Ali kako je sve novce potrošio na turbo moderan čekić, shvatio je da ima novca točno za jednu lampu.
Pošto Mirko želi odabrati neko mjesto s kojeg se vidi cijeli pod, pomozite mu da odredi minimalnu visinu na koju mora podići lampu kako bi osvjetlio cijeli pod špilje.
Pod špilje zamišljamo kao izlomljenu liniju u koordinatnom sustavu koja se sastoji od N vrhova t₁, t₂, ..., t_N, i dužina koje povezuju uzastopne vrhove.
Pod uvijek ide slijeva na desno tj. za svaki i=1, ..., N-1 vrijedi da x koordinata vrha t_i je strogo manja od x koordinate vrha t_i+1.
Primjer (moguće rješenje za treći test primjer):

Lampu je potrebno postaviti negdje u neku točku "iznad" poda špilje, tako da ona osvjetljava cijeli pod. Preciznije rečeno, x koordinata lampe mora se nalaziti između x koordinate prve i zadnje točke poda (uključivo), a y koordinata lampe mora biti veća ili jednaka od y koordinate točke poda s istom x koordinatom.
Kažemo da lampa osvjetljava cijeli pod, ako za svaku točku poda vrijedi da dužina koja povezuje tu točku s lampom ne probada izlomljenu liniju koja predstavlja pod. Ali, dozvoljeno je da se dužina i izlomljena linija poda dodiruju u nekim točkama ili duž nekih segmenata.
Napišite program koji će odrediti najmanju moguću visinu na koju je moguće postaviti lampu tako da osvjetljava cijeli pod.
Možete pretpostaviti da će rješenje uvijek biti manje ili jednako od 1,000,000.