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