#include<bits/stdc++.h>
#define ll long long
#define N 51
#define M 500000
using namespace std;
ll n,a[N],ans,dp[N/2+2][2*M+1],dp2[N/2+2][2*M+1];
ll read(){
    ll x=0,f=1;
    char c=' ';
    while(c>'9'||c<'0'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+(c-'0');
        c=getchar();
    }
    return x*f;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
void dfs(ll l,ll r,ll now,ll s){
    if(dp[l][now+M]>=s) return ;
    dp[l][now+M]=s;
    if(l>r) return ;
    dfs(l+1,r,now+a[l],s+a[l]);
    dfs(l+1,r,now-a[l],s+a[l]);
    dfs(l+1,r,now,s);
    return ;
}
void dfs2(ll l,ll r,ll now,ll s){
    if(l>r){
        ans=max(ans,dp[n/2+1][now+M]+s);
        return ;
    }
    if(dp2[l-n/2][now+M]>=s) return ;
    dp2[l-n/2][now+M]=s;
    if(l>r) return ;
    dfs2(l+1,r,now-a[l],s+a[l]);
    dfs2(l+1,r,now+a[l],s+a[l]);
    dfs2(l+1,r,now,s);
    return ; 
}
int main(){
    freopen("cookie.in","r",stdin);
    freopen("cookie.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=0;i<=n/2+1;i++)
    for(int j=0;j<=2*M;j++) dp[i][j]=dp2[i][j]=-1e18;
    dfs(1,n/2,0,0);
    dfs2(n/2+1,n,0,0);
    write(ans/2);
    return 0;
}