Uolevi ja Maija pelaavat peliä, jossa taulukossa on aluksi $n$ kokonaislukua $x_1,x_2,\ldots,x_n$. Joka vuorolla pelaaja poistaa taulukosta ensimmäisen tai viimeisen luvun ja saa sen pistemäärän itselleen. Tavoitteena on kerätä mahdollisimman suuri kokonaispistemäärä.

Mikä on suurin mahdollinen aloittajan pistemäärä, jos molemmat pelaajat pelaavat optimaalisesti?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: taulukon koko.

Seuraavalla rivillä on $n$ lukua $x_1,x_2,\ldots,x_n$, jotka kuvaavat taulukon sisällön.

Tuloste

Tulosta suurin mahdollinen aloittajan pistemäärä.

Rajat

• $1 \le n \le 1000$
• $-10^9 \le x_i \le 10^9$

Esimerkki

Syöte:

4
4 5 1 3

Tuloste:

8