Гра в картки

Хусейн і Ярослав грають у гру з картками. На столі в рядок розкладено $n$ карток, на кожній з яких написано унікальне число. Гравці ходять по черзі, починаючи з Хусейна. За один хід гравець може взяти або крайню ліву, або крайню праву картку. Гравець завжди вибирає картку з більшим числом. Гра триває, поки на столі не залишиться жодної картки. Визначте суму чисел на картках, які зібрали Хусейн і Ярослав до кінця гри.

Вхідні дані

Перша рядок містить кількість карток $n(1\le n\le 10000)$ на столі. Друга рядок містить $n$ натуральних чисел, записаних на картках. Усі числа не перевищують $10^9$.

Вихідні дані

Виведіть суму чисел на картках, які зібрали Хусейн і Ярослав до кінця гри.

Приклади