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

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

typedef pair<int, int> pii;

pii slv1(int *arr, int len) {
	int ans = 0, dp = 0;
	for (int i = 1; i <= len; i++) {
		dp = max(arr[i], arr[i] + dp);
		ans = max(ans, dp);
	}
	int mx = 0;
	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);
}
pii slv2(int *arr, int len) {
	int ans = 0, dp = 0;
	for (int i = 1; i <= len; i++) {
		dp = max(arr[i], arr[i] + dp);
		ans = max(ans, dp);
	}
	int mx = 0;
	dp = 0;
	for (int i = len; i >= 1; 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;
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 i = 1; i <= L; i++)
		p[i] = i;
	do {
		for (int i = 1; i <= L; i++)
			tmp[i] = a[p[i]];
		pii ttt = slv2(tmp, L);
		if (ttt.first <= ANS)
			A[++tl] = ttt;
	} while (next_permutation(p + 1, p + L + 1));
	
	int tr = 0;
	for (int i = 1; i <= R; i++)
		p[i] = i;
	do {
		for (int i = 1; i <= R; i++)
			tmp[i] = b[p[i]];
		pii ttt = slv1(tmp, R);
		if (ttt.first <= ANS)
			B[++tr] = ttt;
	} while (next_permutation(p + 1, p + R + 1));
	slv(A, tl);
	slv(B, tr);
	int ans = 2e9;
	for (int i = 1, j = 0; i <= tl; i++) {
		while (j < tr && B[j + 1].first <= A[i].first)
			j++;
		if (j)
			ans = min(ans, max(A[i].first, A[i].second + B[j].second));
	}
	for (int i = 1, j = 0; i <= tr; i++) {
		while (j < tl && A[j + 1].first <= B[i].first)
			j++;
		if (j)
			ans = min(ans, max(B[i].first, B[i].second + A[j].second));
	}
	return ans;
}

int arr[N] = {0};



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

int tot = 0;

void dfs(int x) {
	if (x > (n + 1) / 2) {
		++tot;
		if (n > 12 && tot % 7 != 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() {
	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);
	dfs(1);
	cout << ANS << endl;
	return 0;
} 
/*
 6
 4 -4 5 -20 6 7
*/