베시와 보니는 멋진 금화로 가득찬 보물상자를 발견했다! 하지만 그들은 소이기 때문에 그냥 가게에 들어가서 금화를 내고 물건을 살 수가 없었다.

따라서 금화로 할 게 없어진 그들은 금화를 가지고 재밌는 놀이를 하기로 결정했다. 그들은 N (1 <= N <= 5000) 개의 금화를 가지고 있고, 긴 직선에 C_i (1 <= C_i <= 5000) 의 값이 주어져있다. 베시와 보니는 번갈아 가면서 턴을 가지게 되고, 각각의 턴마다 각자 왼쪽 끝이나 오른쪽 끝에 동전 하나를 사용할 수 있다. 게임은 동전이 남지 않게 되면 끝이 난다. 베시와 보니는 서로 가능한 많은 동전을 가지고 싶어한다. 베시가 먼저 게임을 시작하는데, 당신이 할 일은 그녀를 도와 그녀가 이길 수 있는 최상의 경우를 알려주는 것이다. (각각의 소들은 게임에서 최적화된 플레이를 한다.)

만약 4개의 동전과 C_i 의 값이 다음과 같이 주어진다고 하자.

            30  25  10  35

턴 1: 베시는 오른쪽 끝의 35를 가진다. (남은 값들: 30  25  10)
턴 2: 보니는 왼쪽 끝의 30을 가진다. (남은 값들: 25  10)
턴 3: 베시는 왼쪽 끝의 25를 가진다. (남은 값들: 10)
턴 4: 보니는 10을 가진다.

입력

• 첫번째 줄에 N 이 주어진다.
• 두번째 줄부터 N 줄 동안 C_i 값이 주어진다.

출력

입출력 예

입력

4
30
25
10
35

출력

60

출처: USACO 2010 DEC silver
번역: KangJ