#include<iostream>
using namespace std;


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

	int N;	//切れ込みの数
	long long* A;	//一つ一つのバウムクーヘンの大きさ

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

	long long* memo;	//バウムクーヘンの面積をメモ
	void memo_all_piece();	//バウムクーヘンの面積をメモ
	long long sum_baum;	//全てのバウムクーヘンの大きさの和
	double tripartition;	//全てのバウムクーヘンの大きさの三分の一

	long long extended_full_search();	//計算

	long long set_board();		//最初の盤面の作成
	int cut_b;		//2つ目の切れ込み
	int cut_c;		//3つ目の切れ込み

	long long check();	//例外パターンのときの計算
	bool check_bool;	//例外パターンがおきたかどうか

};

baumkuchen::baumkuchen(){
	set = false;
	check_bool = false;
}
baumkuchen::~baumkuchen(){
	if (set)delete[] A;
	if (set)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::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;	//例外パターンのときはcheck()の値を返す

	//一つずつずらしていく
	for (int cut_a = 1; cut_a < 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--;

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

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

		//3つのバウムクーヘンの大きさ比較
		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;	//最大値の更新

		if (cut_c == N || cut_c == 2 * N || cut_c == 3 * N)break;	//切れ込みが重なったらループ終了
	}
	return set_value;
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	baumkuchen *solve = new baumkuchen();
	solve->set_value();
	cout << solve->extended_full_search() << endl;


	delete solve;
	return 0;
}

Measured memory_bytes: 5756