* Fiecare mananca alternativ cate o felie de pizza.
* Alice este cea care alege de unde ia prima felie

* Dupa ce Alice extrage prima felie, fiecare are voie sa aleaga doar o felie adiacenta cu portiunea de pizza deja extrasa.

* Dupa ce Alice extrage prima felie, fiecare are voie sa aleaga doar o felie adiacenta cu o alta felie de pizza deja extrasa.

Fiecare din cei doi copii vor dori sa manance o cantitate cat mai mare de pizza, astfel incat fiecare va avea o strategie optima de extragere a feliilor pentru a manca o catintate maxima posibil de pizza. Se intelege prin cantitate de pizza mancata de unul dintre copii ca suma valorilor de pe feliile de pizza extrase de acesta.

Fiecare din cei doi copii vor dori sa manance o cantitate cat mai mare de pizza, astfel incat fiecare va juca o strategie optima de extragere a feliilor pentru a manca o catintate maxima posibil de pizza. Se intelege prin cantitate de pizza, suma valorilor de pe feliile extrase de unul dintre copii.

Bucatarul este foarte interesat de acest joc al copiilor si va roaga pe voi sa calculati care este valoarea maxima pe care o poate extrage Alice si Bob, fiecare jucand optim si sa ii spuneti diferenta dintre valoarea obtinuta de Alice si valoarea obtinuta de Bob.

h2. Restricţii
* $2 ≤ N ≤ 5 000$

* $1 ≤ X ~i~ ≤ 10 000, unde X ~i~ reprezinta valoarea scrisa pe a i -a felie de pizza$
* $De reţinut faptul ca Antonio şi Antonia iubesc pizza!$

* $1 ≤ X$ ~i~ $≤ 1 000 000$, unde $X$ ~i~ reprezinta valoarea scrisa pe a $i$ -a felie de pizza

h2. Exemplu
table(example). |_. pizza.in |_. pizza.out |

| 7
  7 8 3 10 2 5 7
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

!> problema/pizza?pizza.png 100%!
 
Fiecare copil va juca optim astfel incat se vor extrage pe rand urmatoarele felii de pizza:
 
* Alice: Felia cu numarul $10$
* Bob: Felia cu numarul $2$
* Alice: Felia cu numarul $5$
* Bob: Felia cu numarul $7$
* Alice: Felia cu numarul $7$
* Bob: Felia cu numarul $8$
* Alice: Felia cu numarul $3$
 
Alice extrage felii cu valoarea totala de $25$, iar Bob extrage felii cu valoarea totala de $17$.
Diferenta dintre suma obtinuta de Alice si Bob este $25 - 17 = 8$ .

...

== include(page="template/taskfooter" task_id="pizza") ==

10109