AlgoLiga 2018

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 ≤ 10⁴ oznaczająca liczbę kamieni w rzędzie. Następnie jest n liczb naturalnych. i-ta z tych liczb to 0 < a_i ≤ 10⁹, 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.