#include<iostream>
using namespace std;


class baumkuchen{
public:
	baumkuchen();
	~baumkuchen();

	int N;	//切れ込みの数
	long long* A;	//一つ一つのバウムクーヘンの大きさ
	long long* memo;
	long long sum_baum;	//全てのバウムクーヘンの大きさの和
	double tripartition;

	void set_value();	//値のセット
	bool set;	//値のセットを行ったかどうかを判別する変数

	long long piece(int cut_1, int cut_2);	//3つに切り分けた後のあるひとつのバウムクーヘンの大きさを求める関数
	long long extended_full_search();	//全探索改良版
	long long check();
	bool check_bool;

	void memo_all_piece();
	long long set_board();
	int cut_b;
	int cut_c;

};

baumkuchen::baumkuchen(){
	set = false;
	check_bool = false;
}
baumkuchen::~baumkuchen(){
	if (set == true)delete[] A;
	if (set == true)delete[] memo;
}

void baumkuchen::set_value(){
	sum_baum = 0;
	cin >> N;
	A = new long long[3 * N];
	memo = new long long[3 * N]();

	for (int i = 0; i < N; i++){
		cin >> A[i];			//バウムクーヘンの大きさの入力
		A[N + i] = A[i];
		A[2 * N + i] = A[i];
	}

	memo_all_piece();

	set = true;	//セットの判定
}

void baumkuchen::memo_all_piece(){
	for (int i = 1; i < 3 * N; i++){
		memo[i] = memo[i - 1] + A[i - 1];
	}
	sum_baum = memo[N];	//バウムクーヘンの和
	tripartition = sum_baum / 3.0;	//バウムクーヘンの和の三分の一
}


long long baumkuchen::piece(int cut_1, int cut_2){
	long long piece = 0;
	if (cut_1 > cut_2){
		while (cut_1 != cut_2){
			piece += A[cut_1 - 1];
			cut_1--;
		}
		piece = sum_baum - piece;

	}
	else{
		while (cut_2 != cut_1){
			piece += A[cut_2 - 1];
			cut_2--;
		}
	}
	return piece;
}

long long baumkuchen::check(){
	long long min_value;
	double half = 0.0 + sum_baum;
	half += memo[cut_b] / 2.0;
	
	cut_b = N;
	cut_c = cut_b;
	while (half > memo[cut_c])cut_c++;
	if (half - memo[cut_c - 1] < memo[cut_c] - half)cut_c--;


	if (memo[cut_b] - memo[cut_b - 1] > memo[cut_c] - memo[cut_b]) min_value = memo[cut_c] - memo[cut_b];
	if (memo[cut_c] - memo[cut_b] > (sum_baum + memo[cut_b - 1]) - memo[cut_c]) min_value = (sum_baum + memo[cut_b - 1]) - memo[cut_c];

	check_bool = true;
	return min_value;
}


long long baumkuchen::set_board(){
	long long min_value;

	cut_b = 0;
	while (tripartition > memo[cut_b])cut_b++;
	if (tripartition - memo[cut_b - 1] < memo[cut_b] - tripartition)cut_b--;


	double half = 0.0 + memo[cut_b];
	half += (sum_baum - memo[cut_b]) / 2.0;

	cut_c = cut_b;
	while (half > memo[cut_c])cut_c++;
	if (half - memo[cut_c - 1] < memo[cut_c] - half)cut_c--;

	min_value = memo[cut_b];
	if (min_value > memo[cut_c] - memo[cut_b]) min_value = memo[cut_c] - memo[cut_b];
	if (min_value > sum_baum - memo[cut_c]) min_value = sum_baum - memo[cut_c];
	
	if (cut_b == N - 1) return check();

	return min_value;
}


long long baumkuchen::extended_full_search(){
	long long set_value = 0;
	long long min_value;

	set_value = set_board();
	if (check_bool)return set_value;
	for (int cut_a = 1; cut_a < N; cut_a++){
//		printf("i = %d\n", cut_a);
		while (memo[cut_a] + tripartition > memo[cut_b])cut_b++;
		if (memo[cut_a] + tripartition - memo[cut_b - 1] < memo[cut_b] - (memo[cut_a]+ tripartition))cut_b--;
//		printf("b = %d\n", cut_b);

		double half = 0.0 + memo[cut_b];
		half += (memo[N + cut_a] - memo[cut_b]) / 2.0;
//		printf("half = %f\n", half - memo[cut_b]);

		while (half > memo[cut_c])cut_c++;
		if (half - memo[cut_c - 1] < memo[cut_c] - half)cut_c--;
//		printf("c = %d\n", cut_c);

		min_value = memo[cut_b] - memo[cut_a];
		if (min_value > memo[cut_c] - memo[cut_b]) min_value = memo[cut_c] - memo[cut_b];
		if (min_value > memo[N + cut_a] - memo[cut_c]) min_value = memo[N + cut_a] - memo[cut_c];
		
		if (set_value < min_value)set_value = min_value;
//		printf("set_value = %d\n\n", set_value);

	}
	return set_value;
}

int main(){
	baumkuchen *solve = new baumkuchen();
	solve->set_value();
	long long a = solve->extended_full_search();
	cout << a << endl;


	delete solve;
	return 0;
}

Measured memory_bytes: 5760