/*
Decelerating Jump
https://qoj.ac/problem/2283

DP

*/

#include <stdio.h>

int sqr[3005];
long long mem[3005][3005];
long long tab[3005][3005];

long long max(long long a, long long b){
  long long ans;
  if(a > b)
    ans = a;
  else
    ans = b;
  return ans;
}

long long min(long long a, long long b){
  long long ans;
  if(a < b)
    ans = a;
  else
    ans = b;
  return ans;
}

long long solve(int i, int maxi, int n){
  /* printf("Proc %d, %d\n", i, maxi); */
  long long ans = -1e15, aux;
  int k;

  if(mem[i][maxi] != -1e15)
    ans = mem[i][maxi];
  else{
    if(i == n - 1)
      ans = sqr[i];
    else{
      /* printf("Aca %d, %d\n"); */
      for(k = i + 1; k <= min(n - 1, i + maxi); ++k){
	aux = solve(k, k - i, n);
	if(aux != -1e15){
	  ans = max(ans, aux + sqr[i]);
	  /* printf("Mejor ahora %d, %d es %lli\n", i, maxi, ans); */
	}
      }
    }

    mem[i][maxi] = ans;

    /* printf("Res %d, %d, %lli\n", i, maxi, ans); */
  }
   
  return ans;
}

int main(){
  int i, j, k, n;
  long long ans;
  scanf("%d", &n);
  for(i = 0; i < n; ++i)
    scanf("%d", sqr + i);

  for(i = 0; i < n; ++i)
    tab[i][0] = 0;
  for(i = 0; i < n; ++i)
    tab[n - 1][i] = sqr[n - 1];

  for(i = n - 2; i >= 0; --i){
    for(j = 1; j < n; ++j){
      tab[i][j] = -1e15;
      for(k = i + 1; k <= min(n - 1, i + j); ++k)
	tab[i][j] = max(tab[i][j], tab[k][k - i] + sqr[i]);
    }
  }
  
  ans = tab[0][n - 1];
  printf("%lli\n", ans);
  return 0;
}