\textbf{N} карточек выложены в ряд слева направо. На каждой карточке написано целое число. Два игрока поочередно забирают по одной карточке, причем забирать можно либо крайнюю левую, либо крайнюю правую. Заканчивается игра, когда забраны все карточки (пока карточки есть, игрок обязан делать один из возможных ходов). Цель игры - получить как можно большую сумму (чисел, записанных на забранных карточках). Только вот "играют" в эту игру непонятно зачем начальник-самодур и подчиненный подлиза. Начальник-самодур может целиком и полностью контролировать не только свои ходы, но и ходы подчиненного-подлизы. Какую максимальную сумму сможет набрать начальник-самодур (который, разумеется, ходит первый)? \InputFile В первой строке указано количество карточек \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2013}). Во второй строке через пробелы заданы \textbf{N} целых чисел (не превосходящих по модулю \textbf{10^3}) - значения, записанные на карточках. \OutputFile Выведите единственное целое число - максимальную сумму, которую гарантированно может набрать первый игрок (начальник-самодур). \textit{\textbf{Примечание}}: Поскольку начальник-самодур полностью контролирует ходы подчиненного-подлизы, он может забрать первым ходом \textbf{3}, приказать "сопернику" забирать \textbf{1}.