#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;

const int INF = 1000000000;
const int UNH = 2*INF + 1;
int n;
int a[20];
int c[10000][1024][2][2];

int choose(int turn, int x, int y) {
	if (turn == 0) 
		return max(x,y);
	return min(x,y);
}

int foo(int p[2][2], int mask, int turn, bool fail = false) {
	int z = 0;
	int base = 1;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j) {
			z += base*p[i][j];
			base *= n;
		}
	//if ((z == 877) && (mask == 23) && (turn == 0))
	//	cerr << "here\n";
	if (c[z][mask][turn][fail] != UNH) 
		return c[z][mask][turn][fail];

	int res = -INF + turn * 2*INF;
	bool pp = false;
	for (int i = 0; i < 2; ++i) {
		for (int d = -1; d < 2; d +=2) {
			int op = p[turn][i];
			int omask = mask;
			int curs = 0;
			for (int s = 1; s < n; ++s) {
				int p1 = (p[turn][i] += d);
				if ((p1 < 0) || (p1 >= n)) {
					break;					
				}

				int x = 1 << p1;
				if ((mask & x) != 0) { 					
					break;
				}
				mask += x;
				curs += a[p1];
				res = choose(turn, res, foo(p, mask, 1 - turn) + (turn ? -curs : curs));
				pp = true;
			}
			mask = omask;
			p[turn][i] = op;
		}
	}
	if (!pp) {
		if (fail)
			res = 0;
		else 
			res = foo(p, mask, 1 - turn, true);
	}
	return c[z][mask][turn][fail] = res;

	
}

int main() {
	ifstream fin("fish.in");
	ofstream fout("fish.out");
	
	fin >> n;

	for (int i = 0; i < n; ++i)
		fin >> a[i];

	int ans = -INF;

	int mask = 0;

	for (int i = 0; i < 10000; ++i) 
		for (int j = 0; j < 1024; ++j) 
			for (int k = 0; k < 2; ++k)
				for (int z = 0; z < 2; ++z)
					c[i][j][k][z] = UNH;

	for (int i1 = 0; i1 < n; ++i1) {
		int x1 = 1 << i1;
		if (mask & x1)
			continue;
		mask += x1;
		int m2 = INF;
		for (int j1 = 0; j1 < n; ++j1) {
			int y1 = 1 << j1;
			if (mask & y1)
				continue;
			mask += y1;
//			cerr << mask << "\n";
			int m3 = -INF;
			for (int i2 = 0; i2 < n; ++i2) {
				int x2 = 1 << i2;
				if (mask & x2)
					continue;
				mask += x2;
				int m4 = INF;
				for (int j2 = 0; j2 < n; ++j2) {
					int y2 = 1 << j2;
					if (mask & y2)
						continue;
					mask += y2;
					int p[2][2];
					p[0][0] = min(i1, i2);
					p[0][1] = max(i1, i2);
					p[1][0] = min(j1, j2);
					p[1][1] = max(j1, j2);
					/*
					if ((i1 == 1) && (j1 == 4) && (i2 == 2) && (j2 == 0)) {
						cerr << "here\n";
					}
					*/
					int res = foo(p, mask, 0);					
					res +=  - a[j2] - a[j1] + a[i2] + a[i1];	
					
					
					if (res < m4) {
						m4 = res;
						// cerr << i1 << " " << j1 << " " << i2 << " " << " " << j2 << " " << m4 << "\n";
					}
					mask -= y2;
				}
				
				if (m4 > m3) {
					m3 = m4;
					// cerr << i1 << " " << j1 << " " << i2 << " " << m3 << "\n";
				}
				mask -= x2;
			}
			
			
			if (m3 < m2) {
				m2 = m3;								
				// cerr << i1 << " " << j1 << " " << m2 << "\n";
			}
			
			mask -= y1;
		}
		if (m2 > ans) {			
			ans = m2;
			// cerr << i1 << " " << ans << "\n";			
		}
		mask -= x1;
	}

	fout << ans << "\n";


	return 0;
}