La un concurs de pariuri se prezintă N candidaţi, care se aşază în şir indian în ordinea înscrierii. Fiecare concurent i deţine o sumă de bani a[i] şi primeşte credit încă a[i], deci poate paria dublul sumei pe care o are. Fiind lacomi, concurenţii vor paria de fiecare dată suma plus creditul. Deşi este informaţie secretă, managerul de concurs află valorile acestor sume.
Desemnarea câştigătorului se face în N-1 etape. În fiecare etapă are loc o singură întâlnire, între doi candidaţi vecini. La toate etapele managerul desemnează, dintre concurenţii rămaşi în concurs pe cei doi care se vor întrece. Lupta dintre doi candidaţi este simplă, fiecare dintre ei pariază şi ridică miza cât mai mult. Câştigă cel care mizează valoarea maximă. Câştigătorul etapei îşi creşte suma cu valoarea pariată de cel care a pierdut. Jucătorul câştigător se retrage pe poziţia avută anterior. Cel care pierde iese din concurs. În caz de mize maxime egale câştigătorul este hotărât, prin tragere la sorţi. Regulamentul concursului spune că la final ultimul concurent rămas este câştigătorul concursului şi pleacă acasă cu suma câştigată. Din motive de publicitate, managerul de concurs doreşte să facă în aşa fel încât la final suma câştigată să fie maximă. El poate influenţa acest maxim prin modul cum alege, în fiecare etapă, pe cei doi candidaţi care se întrec.
Cerinţă
Scrieţi un program care să determine suma maximă care poate fi câştigată la concurs.
Date de intrare
Fişierul de intrare pariuri.in conţine pe prima linie numărul natural N, iar pe linia a doua N numere naturale nenule care reprezintă sumele concurenţilor, numerele fiind separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire pariuri.out va conţine o singură linie pe care va fi scrisă suma maximă care poate fi câştigată la concurs.
Restricţii
2 <= N <= 800
1 <= a[i] <= 100 000, pentru 1<=i<=N
Exemple
pariuri.in
pariuri.out
Explicaţie
5
1 5 4 3 2
29
a=(1,5,4,3,2)
La etapa 1 concurează jucătorii 1 şi 2.
Câştigător este 2 şi se obţine a=(0,7,4,3,2)
La etapa 2 concurează jucătorii 4 şi 5.
Câştigător este 4 şi se obţine a=(0,7,4,7,0)
La etapa 3 concurează jucătorii 2 şi 3.
Câştigător este 2 şi se obţine a=(0,15,0,7,0)
La etapa 4 concurează jucătorii 2 şi 4.
Câştigător este 2 şi se obţine a=(0,29,0,0,0) Jucătorii marcaţi în vectorul a cu 0 sunt jucătorii eliminaţi.
