Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_12_09 - Gemmologia

gems

Uwaga: Limit pamięci w zadaniu to 128MB.

Bajtomir niestety stracił wszystkie swoje oszczędności na giełdzie. Problemem nie były programy, których używał do analizy, lecz po prostu grał zbyt odważnie. Zdesperowany postanowił okraść kilka miejsc z kamieni szlachetnych. Jako że samemu nie dałby rady, postanowił wziąć do pomocy swojego brata - Bitomira, który miał już w tym zakresie pewne doświadczenie. Po udanej akcji mieli do podziału n kamieni szlachetnych. Bajtomir szybko zauważył, że jego brat zupełnie nie zna się na gemmologii i bardzo źle wycenia wartość kamieni. Postanowił to wykorzystać i zaproponował mu grę, dzięki której zarobi dużo więcej.

Wszystkie kamienie zostały ustawione w rzędzie. Bracia wykonują ruchy na przemian. Jeden ruch polega na przejęciu na własność kamienia z lewego bądź prawego końca rzędu (tym samym skrócenie rzędu o jeden kamień). Gracz decyduje sam, który kamień wybiera. Bajtomir rusza się jako pierwszy. Jest on wielkim optymistą i chciałby znać największy możliwy zysk, w bajtalarach, jaki może osiągnąć grając w daną grę.

Wejście

Wejście rozpoczyna liczba 1 ≤ n ≤ 104 oznaczająca liczbę kamieni w rzędzie. Następnie jest n liczb naturalnych. i-ta z tych liczb to 0 < a≤ 109, która oznacza wartość i-tego kamienia w rzędzie, w bajtalarach.

Wyjście

Na wyjście należy wypisać jedną liczbę całkowitą, oznaczającą maksymalny możliwy zysk Bajtomira w bajtalarach, po zagraniu w zaproponowaną grę.

Przykład

Wejście:
3
3 5 4
 
Wyjście:
9 Wejście:
5 9 5 8 6 4

Wyjście:
23


Wyjaśnienie do przykładu:
W drugim teście scenariusz, w którym Bajtomir zarobi jak najwięcej jest następujący (po kolei wartości zabieranych kamieni przez graczy): 9, 4, 6, 5, 8. Bajtomir zarobi więc: 9 + 6 + 8 = 23 bajtalarów.


Dodane przez:Adam Bąk
Data dodania:2013-11-22
Limit czasu wykonania programu:1s-1.299s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.