Se dă un șir de N numere întregi notat cu A. O subsecvență a șirului A este un șir Ai Ai+1 Ai+2 ... Aj cu 1 ≤ i ≤ j ≤ N, iar lungimea acestei subsecvențe este egală cu j – i + 1. O operație constă în alegerea unei subsecvențe din șir și ștergerea acesteia. În cadrul unei operații, lungimea subsecvenței alese trebuie să fie o putere de 2. În cadrul tuturor operațiilor efectuate pe șir, lungimile subsecvențelor șterse trebuie să fie distincte.

Pentru fiecare subsecvență din șir considerăm suma elementelor ei. Definim costul unui șir ca fiind maximul acestor sume, în cazul în care șirul conține cel puțin un număr pozitiv, altfel costul șirului este egal cu 0.

Putem aplica o succesiune de operații (eventual niciuna) pe șirul A. În urma acestor operații se vor șterge anumite elemente din șir, obținându-se astfel o mulțime de șiruri M={A, A’1 , A’2, A’3 , ...}.

Cerința

Să se determine costul maxim posibil ce se poate obține dintr-un șir al mulțimii M.

Date de intrare

Fișierul de intrare recyclebin.in conține pe prima linie un număr întreg N. A doua linie conține N numere întregi, separate prin câte un spațiu, reprezentând valorile șirului A.

Date de ieșire

Fișierul de ieșire recyclebin.out va conține pe prima linie valoarea costului maxim.

Restricții și precizări

• 1 ≤ N ≤ 1000
• -106 ≤ Ai ≤ 106 pentru 1 ≤ i ≤ N
• Pentru teste în valoare de 10 puncte 1 ≤ N ≤ 30
• Pentru alte teste în valoare de 15 puncte se garantează că există o soluție cu cel mult o operație efectuată
• Pentru alte teste în valoare de 20 puncte se garantează că există o soluție cu cel mult două operații efectuate
• În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemplu.

Exemplu

recyclebin.in

14
13 -19 13 -5 -12 11 20 4 -10 1 -7 19 -19 3

recyclebin.out

76

Explicație

Șirul inițial este: [13 -19 13 -5 -12 11 20 (4 -10 1 -7) 19 -19 3].
De la poziția 8 ștergem 4 elemente, șirul rezultat este [13 -19 13 (-5 -12) 11 20 19 -19 3]
De la poziția 4 ștergem 2 elemente, șirul rezultat este [13 (-19) 13 11 20 19 -19 3].
De la poziția 2 ștergem un element, șirul rezultat este [13 13 11 20 19 -19 3].
Subsecvența de sumă maximă din șirul final este [13 13 11 20 19].