Legenda spune că, acum mult timp, în orașul Suceava ar fi fost îngropată o comoară de o valoare infinită. Fascinat de această teorie, ai decis să îți încerci și tu norocul.
Din fericire, amatorii de arheologie de pe site-urile de socializare au propus o listă de N locații populare pentru îngroparea comorilor, toate fiind plasate în linie, de-a lungul plaiurilor Sucevei. Mai mult, ai găsit pe internet o aplicație de detectat comori profesională, a cărei radar pretinde să aibă o putere infinită de detectare și în care poate fi inclusiv setată comoara care se caută!
Problema este că această aplicație consumă bateria telefonului, iar tu îți dorești să fii econom, așa că ai decis să nu menții telefonul aprins încontinuu, ci să îl aprinzi doar în diferite locații posibile. Astfel, tu poți alege să mergi către o locație și să îl aprinzi. Aplicația îți va spune dacă în acel loc este comoara, sau, în caz contrar, îți va arăta direcția către aceasta. Această direcție poate fi spre dreapta sau spre stânga, în funcție de locația adevărată a comorii.
Din păcate, din cauza descărcărilor electrostatice din aer, în funcție de locul în care decizi să detectezi comoara, aplicația poate necesita mai mult timp de calibrare, astfel consumând mai multă baterie. Mai exact, pentru a aprinde detectorul în locația i, vei consuma unități de baterie. Tu nu știi unde este îngropată comoara, de aceea vrei să te asiguri că telefonul nu va rămâne fără baterie fără să găsești comoara, oriunde ar fi aceasta îngropată.
Cerință
Dându-se numărul de unități de baterie consumate pentru fiecare dintre cele N locații, care este numărul minim de unități de baterie de care vei avea nevoie, astfel încât să găsești cu siguranță comoara folosind detectorul, oriunde s-ar afla, înainte ca telefonul să rămână fără baterie?
Date de intrare
Pe prima linie a fișierului de intrare takara.in se află un număr întreg pozitiv N, reprezentând numărul de locații posibile. Pe a doua linie se află N numere întregi pozitive , separate prin spații, cu semnificațiile din enunț.
Date de ieșire
Pe prima linie a fișierului de ieșire takara.out se va afla un singur număr întreg pozitiv, reprezentând numărul minim de unități de baterie necesar pentru a afla locația comorii, oriunde s-ar afla aceasta.
Restricții
1 ≤ N ≤ 5 000- Pentru teste în valoare de
15puncte,1 ≤ N ≤ 500 - Pentru alte teste în valoare de
55de puncte,1 ≤ N ≤ 2 000
Exemple
takara.in
4
10 1 5 2
takara.out
3
Explicație
Începi prin a verifica locația 2, consumând o unitate de baterie.
Dacă aplicația te va direcționa spre stânga, vei ști că locația comorii este 1.
Dacă te va direcționa spre dreapta, vei verifica locația 4, consumând încă două unități.
După aceasta, vei ști sigur unde se află comoara.
takara.in
6
73 33 44 25 6 70
takara.out
58
takara.in
9
91 35 21 55 30 45 53 29 91
takara.out
96
takara.in
20
18 32 37 17 22 13 3 35 20 30 37 32 10 23 9 5 27 36 27 22
takara.out
65