На листке записано n (2 ≤ n ≤ 100, n четное) целых положительных чисел. Каждое число не превышает 200. Играют двое. За каждый ход можно зачеркнуть крайнее число либо слева, либо справа. Зачеркнутое число добавляется к очкам игрока.

Выведите максимально возможную сумму очков для первого игрока при условии, что противник играет наилучшим образом.

Входные данные

В первой строке содержится одно целое число n (2 ≤ n ≤ 100, n четное). В следующих n строках записан исходный ряд чисел, по одному числу в строке.

Выходные данные

Выведите максимально возможную сумму очков для первого игрока при наилучшей игре второго игрока.