#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
    int n;
    cin >> n;
    V<int> a(n);
    rep(i,n) cin >> a[i];
    V<ll> sums(n+1);
    sums[1] = a[0];
    for(int i = 2; i <= n; i++) {
        sums[i] = a[i-1] + sums[i-1];
    }
    ll ans = infll;
    for(int i = 2; i <= n-2; i++) {

        auto func = [&](int L, int R) {
            int l = L; int r = R;
            while(abs(r-l) > 1) {
                int mid = (r+l)/2;
                ll p = sums[mid]-sums[L];
                ll q = sums[R]-sums[mid];
                if(p < q) l = mid;
                else r = mid;
            }
            Pl res;
            if(abs((sums[l]-sums[L])-(sums[R]-sums[l])) > abs((sums[r]-sums[L])-(sums[R]-sums[r])))
                res = make_pair(sums[r]-sums[L], sums[R]-sums[r]);
            else
                res = make_pair(sums[l]-sums[L], sums[R]-sums[l]);
            return res;
        };

        Pl a = func(0,i);
        Pl b = func(i,n);
        ll tmp = max({a.fi, a.se, b.fi, b.se}) - min({a.fi, a.se, b.fi, b.se});
        chmin(ans, tmp);
    }
    cout << ans << endl;
}
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "{";
	rep(i, v.size()) {
		if (i) os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}
template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >>p.second ;
	return is;
}
template <class T>istream& operator>>(istream& is,  vector<T>& v) {
	rep(i, v.size()) {
		is >> v[i];
	}
	return is;
}
ll mod                = 1e9 + 7;
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n;
	ll ans=1LL;
	cin >>n;
	Vi a(n);
	cin >> a;
	map<int, ll> dis;
	dis[-1] = 3LL;
	rep(i, n) {
		ans *= dis[a[i] - 1LL];
		ans %= mod;
		dis[a[i]]++;
		dis[a[i] - 1]--;
	}
	cout<<ans<<endl;
}