Соревнования
БГУ Личное Первенство
Игра в карточки
Хусейн с Ярославом играют в карточки. На столе в ряд лежат n карточек, на которых написаны различные числа. Ходят по очереди. Первым ходит Хусейн. За один ход игрок может взять или крайнюю слева карточку, или крайнюю справа. Игрок всегда берет карточку с большим числом. Игра заканчивается, когда карт на столе не останется. Выведите сумму чисел на карточках Хусейна и Ярослава.
Входные данные
Первая строка содержит количество карточек n\:(1 \le n \le 10000) на столе. Вторая строка содержит n натуральных чисел, записанных на карточках. Все числа не больше 10^9.
Выходные данные
Выведите сумму чисел на карточках Хусейна и Ярослава по окончанию игры.
Пример
Входные данные #1
7 4 7 5 1 12 8 2
Выходные данные #1
18 21