#include <iostream>
using namespace std;
const int N=202;
int dp[N][N],a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=0;i<=n+1;i++){
for(int j=0;j<=n+1;j++)
{
dp[i][j]=-1e9;
}
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i][i]=a[i];
}
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int p=l;p<r;p++)
{
dp[l][r]=max(dp[l][r],(dp[l][p]+dp[p+1][r])/2);
}
dp[l][r]=max(dp[l][r],(dp[l+2][r]+((a[l]+a[l+1])/2))/2);
dp[l][r]=max(dp[l][r],(dp[l][r-2]+((a[r]+a[r-1])/2))/2);
for(int p=l+1;p+1<r;p++)
{
int a0=dp[l][p-1];
int a1=(a[p]+a[p+1])/2;
int a2=dp[p+2][r];
int a01=(a0+a1)/2;
int a12=(a1+a2)/2;
dp[l][r]=max(dp[l][r],(a01+a2)/2);
dp[l][r]=max(dp[l][r],(a12+a0)/2);
}
}
}
cout<<dp[1][n]<<endl;
}
