takara

Time limit: 0.6s Memory limit: 512MB Input: takara.in Output: takara.out

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 CiC_i 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 CiC_i, 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
  • 1Ci200 0001 ≤ C_i ≤ 200 \ 000
  • Pentru teste în valoare de 15 puncte, 1 ≤ N ≤ 500
  • Pentru alte teste în valoare de 55 de 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

Log in or sign up to be able to send submissions!