Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kortų žaidimas

Ant stalo iš eilės padėta n kortų. Ant kiekvienos kortos yra užrašytas skaičius a_i. Augustinas ir Vytautas paeiliui žaidžia kortų žaidimą. Pirmuoju ėjimu Augustinas išsirenka arba pačią kairiausiąją kortą, arba pačią dešiniausiąją kortą iš eilės, ir ją pasiima. Tada Vytautas padaro tą patį: išsirenka vieną kortą iš kažkurio kortų eilės galo ir ją pasiima. Abu žaidėjai visada renkasi tą kortą, ant kurios užrašytas skaičius yra didesnis. Taip žaidėjai paeiliui ima kortas, kol jų ant stalo nebelieka. Laimi tas žaidėjas, kurio pasiimtų kortų suma, paėmus visas kortas, yra didesnė.

Pavyzdžiui, jei ant stalo yra kortos (tokia eilės tvarka): 2, 3, 1, tai žaidimas vyks taip:

  • Augustinas pasiima kairiausiąją kortą, nes 2>1, lieka kortos 3, 1.
  • Vytautas pasiima kairiausiąja kortą, nes 3>1, lieka viena korta 1.
  • Augustinas pasiima vienintelę likusią kortą.
Augustino kortų suma 3, o Vytauto, taip pat 3.

Jūsų užduotis - išvesti ant abiejų žaidėjų kortų parašytų skaičių sumas!

Pradiniai duomenys

Pirmoje eilutėje pateiktas skaičius n. Antroje eilutėje pateikta n tarpais atskirtų sveikųjų skaičių a_1,a_2,...a_n. Visi a_i skirtingi.

Rezultatai

Jūsų programa turi atspausdinti du skaičius, atskirtus tarpais: Augustino ir Vytauto kortų sumas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
3 4 1 2
 
5 5
 
5
6 3 2 5 4
 
13 7

Ribojimai

1\\leqn\\leq10^5, 1\\leqa_i\\leq10^6. Atsakymai gali netilpti į int kintąmojo tipą, todėl nepamirškite naudoti long long!