#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ins insert
#define pq priority_queue
#define minele min_element
#define maxele max_element
#define lb lower_bound //first pos >= val
#define ub upper_bound // first pos > val
#define cnt_bit __builtin_popcount
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

const ll oo = 1e18;
const ll maxN = 1e6;

/* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */

void maximize(int &a, int b) {
    a = max(a, b);
}

void minimize(int &a, int b) {
    a = min(a, b);
}

ll ans = oo;
int n;
ll a[120];

void dp(int id, ll x, ll y, ll z) {
    if(id > n) {
        ans = min(ans, max({x, y, z}) - min({x, y, z}));
        return;
    }

    dp(id + 1, x + a[id], y, z);
    dp(id + 1, x, y + a[id], z);
    dp(id + 1, x, y, z + a[id]);
}

ll candy[10];
bool f[104][2010][2010];
const int l = 2000;
ll d[(1 << 20) + 10];

void solve() {
    cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    if(n <= 15) {
        dp(1, 0, 0, 0);
        cout << ans;
    } else {
        if(sum <= l) {
            f[0][0][0] = true;
            for(int i = 1; i <= n; i++) {
                for(int x = 0; x <= l; x++) {
                    for(int y = 0; y <= l; y++) {
                        f[i][x][y] = f[i - 1][x][y];
                        if(f[i][x][y]) continue;
                        if(x >= a[i]) {
                            f[i][x][y] |= f[i - 1][x - a[i]][y];
                        }

                        if(y >= a[i]) {
                            f[i][x][y] |= f[i - 1][x][y - a[i]];
                        }
                    }
                }
            }

            int ans = 1e9;
            for(int x = 0; x <= l; x++) {
                for(int y = 0; y <= l; y++) {
                    if(!f[n][x][y]) continue;
                    int z = sum - x - y;
                    ans = min(ans, max({x, y, z}) - min({x, y, z}));
                }
            }

            cout << ans;
        } else {
            auto Mask = [&](int id) -> int {
                return (1 << (n - id));
            };

            ll tot = 0;
            for(int i = 1; i <= n; i++) tot = tot + a[i];

            for(int msk = 0; msk < (1 << n); msk++) {
                ll sum = 0;
                for(int i = 1; i <= n; i++) {
                    if(msk & Mask(i)) {
                        if(d[msk ^ Mask(i)] + a[i] <= tot / 3) {
                            d[msk] = max(d[msk], d[msk ^ Mask(i)] + a[i]);
                        } else {
                            d[msk] = max(d[msk], d[msk ^ Mask(i)]);
                        }

                        sum = sum + a[i];
                    }
                }


                ll B = tot - sum;
                ll A = d[msk];
                ll C = sum - A;
                ans = min(ans, max({A, B, C}) - min({A, B, C}));
            }

            cout << ans;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else
    //online
    #endif

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        solve();
    }
}