\textbf{N} cards laid out in a row from left to right. There is some integer on each card. Two players alternately take cards, one by one, and they can only take either the left or the right card of a row. The game ends when all the cards are taken (as long as there are cards, the player must do one of the possible turnes). The aim of the game - get the biggest sum of integers, written on taken cards. It is not clear why boss-tyrant and slave-toady ѕplayї this game. Boss-tyrant can fully control not only his moves, but moves of the slave-toady. What the maximum sum the boss-tyrant can achieve through a single game (Which, of course, starts from his majestic move)? \InputFile The first line consists the number of cards \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2013}). The second line consists \textbf{N}\textit{ }integers (not exceeding the module of \textbf{10^3}) - the values written on the cards. \OutputFile Output the single integer - maximum sum the boss-tyrant is guaranteed to achieve through a single game. \textit{\textbf{Note}}: As boss-tyrant has full control of the slave-toady moves, he can take \textbf{3}, order ѕthe opponentї to take \textbf{1}, and then picks \textbf{9} (so he get \textbf{3 + 9 = 12}), after that the slave-toady takes \textbf{2} and thus ѕthe fairest game everї ends.