Թվեր հեռացնելու խաղը

Եկեք խաղ խաղանք։ Ձեզ տրված է n դրական ամբողջ թվերից բաղկացած հաջորդականություն (որտեղ n-ը զույգ է)։ Յուրաքանչյուր քայլին թույլատրվում է հեռացնել թվերի շարքի սկզբից կամ վերջից մեկ թիվ և այն պահել ձեզ մոտ։ Ես (համակարգչը) կջնջեմ սկզբի և վերջի թվերից ամենամեծը։ Եթե այդ թվերը հավասար են, ես կհեռացնեմ առաջինը։ Մենք հերթով կխաղանք այս խաղը մինչև հաջորդականության բոլոր թվերը չվերջանան։

Խաղը սկսում եք դուք։ Ի՞նչ առավելագույն գումար կարող եք հավաքել։

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤ 1000)։

Հաջորդ տողում տրված են n ամբողջ թվեր (1 ≤ ≤ ), որոնք բաժանված են բացատներով։

Ելք

Ծրագիրը պետք է տպի այն առավելագույն գումարը, որը կարող եք հավաքել։

Օրինակներ

Բացատրություն

1. Դուք վերցնում եք առաջին 3-ը → 2 10 4

2. Համակարգիչը վերցնում է 4-ը → 2 10

3. Դուք վերցնում եք 10-ը → 2

4. Համակարգիչը վերցնում է 2-ը ⇒ Դուք հավաքում եք 3 + 10 = 13