#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const int inf = ~0x3f3f3f3f;

int n;
int a[N] = {0};
int b[N] = {0};

typedef pair<int, int> pii;

pii slv1(int *arr, int len) {
	int ans = inf, dp = inf;
	for (int i = 1; i <= len; i++) {
		dp = max(arr[i], arr[i] + dp);
		ans = max(ans, dp);
	}
	int mx = inf;
	dp = 0;
	for (int i = 1; i <= len; i++)
		dp += arr[i], mx = max(mx, dp);
		
//	for (int i = 1; i <= len; i++)
//		cout << arr[i] << " ";
//	cout << " ?? " << ans << " " << mx << endl;
		
	return make_pair(ans, mx);
}

int p[N] = {0};
int tmp[N] = {0};

const int M = 5e4 + 5;

int allL[M][N] = {{0}};
int totl, totr;
int allR[M][N] = {{0}};


pii A[M], B[M];
pii C[M];

int ANS = 2e9;

void slv(pii *arr, int &len) {
	sort(arr + 1, arr + len + 1);
	int mn = 2e9, cur = 0;
	for (int i = 1; i <= len; i++)
		if (arr[i].second < mn)
			mn = arr[i].second, C[++cur] = arr[i];
	len = cur;
	for (int i = 1; i <= cur; i++)
		arr[i] = C[i];
}

int calc() {
	int L = (n + 1) / 2;
	int R = n - L;
	int tl = 0;
	for (int t = 1; t <= totl; t++) {
		for (int i = 1; i <= L; i++)
			tmp[i] = a[allL[t][i]];
		pii ttt = slv1(tmp, L);
		if (ttt.first <= ANS)
			A[++tl] = ttt;
	}
	
	int tr = 0;
	for (int t = 1; t <= totr; t++) {
		for (int i = 1; i <= R; i++)
			tmp[i] = b[allR[t][i]];
		pii ttt = slv1(tmp, R);
		if (ttt.first <= ANS)
			B[++tr] = ttt;
	}
//	slv(A, tl);
//	slv(B, tr);
	sort(A + 1, A + tl + 1);
	sort(B + 1, B + tr + 1);
	int ans = 2e9;
	for (int i = 1, j = 0, mn = 2e9; i <= tl; i++) {
		while (j < tr && B[j + 1].first <= A[i].first)
			j++, mn = min(mn, B[j].second);
		if (j)
			ans = min(ans, max(A[i].first, A[i].second + mn));
	}
	for (int i = 1, j = 0, mn = 2e9; i <= tr; i++) {
		while (j < tl && A[j + 1].first <= B[i].first)
			j++, mn = min(mn, A[j].second);
		if (j)
			ans = min(ans, max(B[i].first, B[i].second + mn));
	}
	return ans;
}

int arr[N] = {0};



int chose[N] = {0};
bool vis[N] = {false};

int tot = 0;

clock_t stclock = 0;

void dfs(int x) {
	if (1.0 * (clock() - stclock) / CLOCKS_PER_SEC > 1) {
		cout << ANS;
		exit(0);
	}
	if (x > (n + 1) / 2) {
		++tot;
	//	if ((14 <= n && n <= 15 && tot % 5 != 0) || (n == 16 && tot % 15 != 0))
	//		return;
	
		for (int i = 1; i <= (n + 1) / 2; i++)	
			a[i] = arr[chose[i]];
		for (int i = 1, j = 0; i <= n; i++)
			if (!vis[i])
				b[++j] = arr[i];
		ANS = min(ANS, calc());
		return;
	}
	for (int i = chose[x - 1] + 1; i <= n; i++) {
		chose[x] = i;
		vis[i] = true;
		dfs(x + 1);
		vis[i] = false;
		if (x == 1)
			return;
	}
}

int main() {
	stclock = clock();
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &arr[i]);
	mt19937 myrand(time(0));
	shuffle(arr + 1, arr + n + 1, myrand);
	
	int L = (n + 1) / 2, R = n - L;
	for (int i = 1; i <= L; i++)
		p[i] = i;
	do {
		++totl;
		for (int i = 1; i <= L; i++)
			allL[totl][i] = p[i];
	} while (next_permutation(p + 1, p + L + 1));
	
	for (int i = 1; i <= R; i++)
		p[i] = i;
	do {
		++totr;
		for (int i = 1; i <= R; i++)
			allR[totr][i] = p[i];
	} while (next_permutation(p + 1, p + R + 1));
	
	dfs(1);
	cout << ANS << endl;
	return 0;
} 
/*
 6
 4 -4 5 -20 6 7
*/