Un grup de N îngeraşi s-au adunat în cerc - fiecare dintre ei stă pe un norişor aflat la o anumită înălţime, cunoscută. Norişorii sunt numerotaţi în ordine de la 1 la N. Îngeraşii vor sta de vorbă ″de la egal la egal″ şi, urmărind să fie la aceeaşi înălţime, nu pierd ocazia de a se juca un pic. Jocul constă în a-şi face cu ochiul unul altuia într-o anumită ordine: ″emiţătorul″ va fi îngeraşul care este cel mai aproape de pământ, iar dacă sunt mai mulţi la aceeaşi înălţime minimă, atunci va emite cel care stă pe norişorul cu numărul de ordine cel mai mic.
Emiţătorul va privi spre toţi ceilalţi, în ordine, şi va face cu ochiul doar celor aflaţi mai sus decât el: îngeraşul care a primit semnalul va reduce înălţimea norişorului propriu cu o valoare egală cu înălţimea la care se află norişorul îngeraşului care a trimis semnalul.
În etapa următoare se alege un nou emiţător (după aceeaşi regulă) care va relua seria de “clipiri”. Într-o etapă emiţătorul va face cu ochiul o singură dată fiecărui îngeraş (dacă acesta este situat mai sus decât el).
Jocul continuă până când, după un număr de astfel de etape, toţi îngeraşii vor ajunge la aceeaşi înălţime, H.
Cerinţă
Să se scrie un program care calculează şi afişează înălţimea finală H.
Date de intrare
De pe prima linie a fişierului de intrare ingerasi.in se citeşte un număr natural N reprezentând numărul de îngeraşi.
Următoarele N linii a fişierului de intrare conţin câte un număr natural, reprezentând înălţimile norişorilor.
Date de ieşire
Pe prima linie a fişierului de ieşire ingerasi.out se va afişa valoarea H, reprezentând înălţimea la care se află în final norişorii.
Restricţii
1<=N<=30
Înălţimile norişorilor sunt numere naturale cuprinse între 1 şi 1000000000
Exemple
ingerasi.in
ingerasi.out
Explicaţii
3
12
4
10
2
În prima etapă 2 este emiţător (la înălţimea 4):
- 2 îi face cu ochiul lui 1 şi acesta va ajunge la înălţimea 12-4=8
- 2 îi face cu ochiul lui 3 şi acesta va ajunge la înălţimea 10-4=6
În a doua etapă tot 2 este emiţător (la înălţimea 4):
- 2 îi face cu ochiul lui 1 şi acesta va ajunge la înălţimea 8-4=4
- 2 îi face cu ochiul lui 3 şi acesta va ajunge la înălţimea 6-4=2
În a treia etapă 3 este emiţător (la înălţimea 2):
- 3 îi face cu ochiul lui 1 şi acesta va ajunge la înălţimea 4-2=2
- 3 îi face cu ochiul lui 2 şi acesta va ajunge la înălţimea 4-2=2.
Jocul se încheie pentru că toţi îngeraşii sunt la aceeaşi înălţime H=2.