Zadanie

Ešteže na nadpise nezáleží

Počet bodov: 40

Hodobox veľmi rád ponocuje. Ak sa do druhej ráno nehrá Ligu Leguánov, ani nepozerá anime, pravdepodobne leží v posteli a vymýšľa úlohy. Tak napríklad: Ak máme pred sebou niekoľko kartičiek s číslami a necháme dvoch hráčov postupne ťahať po jednej kartičke buď zprava alebo zľava, koľko bodov (súčet čísiel na kartičkách) budú mať hráči po tom, čo bude zobratá posledná kartička? Samozrejme, predpokladáme, že cieľom je mať čo najvyšší počet bodov a obaja hráči hrajú optimálne (t.j. obaja vedia plánovať dopredu, vedia že aj ich protihráč spraví najlepší ťah, a vždy spravia ten ťah ktorý im zaručí že na konci budú mať najviac bodov, ako je možné).

Po úlohe Hodobox napísal aj vstupy. Dokonca napísal aj výstupy.

Ale keďže budík zvoní za 4 hodiny a 23 minút, bolo by pre všetkých najlepšie, ak by ste riešenie napísali vy.

Vstup a výstup

Na prvom riadku vstupu sa nachádza číslo \(N\), ktoré predstavuje počet kartičiek s číslami.

Následuje \(N\) medzerou oddelených čísiel \(M_i\) reprezentujúcich jednotlivé kartičky.

Vypíšte, koľko bodov budú mať obaja hráči na konci hry, ak obaja hrajú optimálne.

Vypíšte najskôr body hráča, ktorý ťahal prvý a potom body hráča, ktorý ťahal druhý, oddelené medzerou.

Platí:

\(1 \leq M_i \leq 1000\).

V prvej sade \(1 \leq N \leq 15\).

V druhej sade \(1 \leq N \leq 100\).

V tretej sade \(1 \leq N \leq 1200\).

Príklad

Input:

5 
8 2 3 4 5

Output:

14 8

V prvom ťahu sa prvému hráčovi najviac oplatí zobrať číslo 8 a druhý hráč následne berie číslo 5. Potom sa prvému hráčovi oplatí zobrať číslo 4 a druhý berie číslo 3. Pri poslendom ťahu už prvá hráč nemá na výber, a tak berie poslednú kartičku s číslom 2. Ak by ktorýkoľvek hráč spravil iné rozhodnutie, protihráčovi by sa len ušlo viac bodov, a nám menej. 8+4+2 = 14 a 5+3 = 8.