카드 게임

알베르토와 완데를레이가 카드 게임을 한다. 정수가 하나씩 적힌 카드가 짝수 개 있고, 이 카드는 탁자 위에 한 줄로 나란히 놓여 하나의 수열을 이룬다. 먼저 알베르토가 양쪽 끝에 있는 두 카드 중 하나를 가져간다. 이어서 완데를레이가 남은 카드의 양쪽 끝 중 하나를 가져가고, 다시 알베르토가 끝에 있는 카드 하나를 가져간다. 이렇게 번갈아 진행하다가 완데를레이가 마지막 카드를 가져가면 게임이 끝난다.

먼저 시작하는 알베르토는 자신이 가져간 카드에 적힌 수의 합, 즉 자신의 점수를 최대로 만들려고 한다. 두 번째로 두는 완데를레이는 알베르토를 방해해서 알베르토의 점수를 최소로 만들려고 한다. 두 사람 모두 각자의 목표에 맞게 최선으로 둔다.

카드의 수열이 주어졌을 때, 알베르토가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어지고, 각 테스트 케이스는 두 줄이다. 첫째 줄에는 탁자 위에 놓인 카드의 개수 $N$이 주어진다. 둘째 줄에는 카드에 적힌 $N$개의 정수가 놓인 순서대로 주어진다. 테스트 케이스는 입력의 끝까지 이어진다.

제약

• $2 \le N \le 10^4$
• $N$은 짝수다
• 각 카드에 적힌 정수는 32비트 부호 있는 정수로 나타낼 수 있다
• 테스트 케이스는 20개 이하이고, 모든 테스트 케이스의 $N$을 더한 값은 $2 \times 10^4$ 이하다

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 정수는 알베르토가 얻을 수 있는 점수의 최댓값이다.