#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using boost::adaptors::reversed;
using boost::irange;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;




int main() {
    ll N;
    cin >> N;
    vector<ll> as(N);
    for (auto && i: irange(0LL, N)){
        ll a;
        cin >> a;
        a *= 2;
        as.at(i) = a;
    }
    vector<ll> as_acc(N+1, 0);
    for (auto && i: irange(1LL, N+1)){
        as_acc.at(i) = as_acc.at(i-1) + as.at(i-1);
    }

    ll ret{numeric_limits<ll>::max()};
    for (auto && idx_3rd_start: irange(2LL, N-1)){
        ll s_former_half = as_acc.at(idx_3rd_start);
        ll s_latter_half = as_acc.back() - s_former_half;
        ll idx_2nd_start_candidate_latter = distance(as_acc.begin(), lower_bound(as_acc.begin(), as_acc.begin()+idx_3rd_start, s_former_half / 2));
        ll idx_2nd_start_candidate_former = idx_2nd_start_candidate_latter - 1;
        ll idx_2nd_start;
        if (idx_2nd_start_candidate_latter == idx_3rd_start){
            idx_2nd_start = idx_2nd_start_candidate_former;
        } else {
            ll sum_1st_former = as_acc.at(idx_2nd_start_candidate_former);
            ll sum_2nd_former = as_acc.at(idx_3rd_start) - as_acc.at(idx_2nd_start_candidate_former);
            ll sum_1st_latter = as_acc.at(idx_2nd_start_candidate_latter);
            ll sum_2nd_latter = as_acc.at(idx_3rd_start) - as_acc.at(idx_2nd_start_candidate_latter);
            if (abs(sum_1st_former - sum_2nd_former) > abs(sum_1st_latter - sum_2nd_latter)){
                idx_2nd_start = idx_2nd_start_candidate_latter;
            } else {
                idx_2nd_start = idx_2nd_start_candidate_former;
            }
        }

        ll idx_4th_start_candidate_latter = distance(as_acc.begin(), lower_bound(as_acc.begin()+idx_3rd_start, as_acc.end(), s_former_half + s_latter_half / 2));
        ll idx_4th_start_candidate_former = idx_4th_start_candidate_latter - 1;
        ll idx_4th_start;
        if (idx_4th_start_candidate_latter == N+1){
            idx_4th_start = idx_4th_start_candidate_former;
        } else {
            ll sum_3rd_former = as_acc.at(idx_4th_start_candidate_former) - as_acc.at(idx_3rd_start);
            ll sum_4th_former = as_acc.back() - as_acc.at(idx_4th_start_candidate_former);
            ll sum_3rd_latter = as_acc.at(idx_4th_start_candidate_latter) - as_acc.at(idx_3rd_start);
            ll sum_4th_latter = as_acc.back() - as_acc.at(idx_4th_start_candidate_latter);
            if (abs(sum_3rd_former - sum_4th_former) > abs(sum_3rd_latter - sum_4th_latter)){
                idx_4th_start = idx_4th_start_candidate_latter;
            } else {
                idx_4th_start = idx_4th_start_candidate_former;
            }
        }

        ll sum_1st = as_acc.at(idx_2nd_start);
        ll sum_2nd = as_acc.at(idx_3rd_start) - as_acc.at(idx_2nd_start);
        ll sum_3rd = as_acc.at(idx_4th_start) - as_acc.at(idx_3rd_start);
        ll sum_4th = as_acc.back() - as_acc.at(idx_4th_start);
        ll hoge = max(abs(sum_1st - sum_2nd), max(abs(sum_1st - sum_3rd), max(abs(sum_1st - sum_4th), max(abs(sum_2nd - sum_3rd), max(abs(sum_2nd - sum_4th), abs(sum_3rd - sum_4th))))));
        ret = min(ret, hoge);
    }
    cout << ret / 2;
}

Measured memory_bytes: 3328