• HOME
• ACTIVITIES
• OLYMPIAD
• MEMBERS
• ABOUT

Related:

• Overview
• Current
• Study Material
• Online Judge
• Archives

Zonal Computing Olympiad 2011, 4 Dec 2010

10:00 am–1:00 pm IST

Problem 2 : Number Game

Here is a game that you play against a friend. You are given a list of numbers. You move first and pick either the first or the last number from the list, which is then removed from the list. Your friend moves next and again picks either the first or the last number from the list that remains. You move alternately in this manner till all the numbers in the list have been picked.

Your score at the end of the game is the sum of numbers that you have picked. Your friend is a master of the game and will always play to ensure that your total score is as small as possible. Your aim is to compute your maximum score under these circumstances.

For instance, suppose that the sequence of numbers is the following.

2,5,3,3,2,1

In this case, the maximum score you can obtain is 9. To achieve this, you pick 1 in the first round. This forces your opponent to pick one of the 2's. Depending on which 2 he picks, you can either pick 5 in the second round and 3 in the third round or 3 in the second round and 5 in the third round.

Input format

The first line of input is an integer N, the length of the sequence. The second line contains N integers, the sequence on which the game is played.

Output format

A single line with a single integer indicating the maximum score you can achieve.

Testdata

You may assume that 1 ≤ N ≤ 2000. Each number in the sequence is in the range [-2000,2000].

Sample Input

6
2 5 3 3 2 1

Sample Output

9

Time and memory limits

The time limit for this task is 2 seconds. The memory limit is 64MB.