unittest
{
	assert( [ "5", "3 2 4 1 2" ].parse.expand.solve == 2 );
	assert( [ "10", "10 71 84 33 6 47 23 25 52 64" ].parse.expand.solve == 36 );
	assert( [ "7", "1 2 3 1000000000 4 5 6" ].parse.expand.solve == 999999994 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( as );
}

auto solve( long[] as )
{
	// 累積和表に変換
	as = 0 ~ as;
	for( auto i = 1L; i < as.length; i++ )
	{
		as[ i ] += as[ i - 1 ];
	}
	
	// QとRの境界を仮置き
	auto ans = long.max;
	auto cs = [ 0L, 1L, 2L, 3L, as.length.signed - 1 ];
	for( ; cs[ 2 ] + 2 < as.length; cs[ 2 ]++ )
	{
		// PとQの差が最小になる境界を探索
		for( auto c = cs[ 1 ], e = long.max; c < cs[ 2 ]; c++ )
		{
			auto p = as[ c ] - as[ cs[ 0 ] ];
			auto q = as[ cs[ 2 ] ] - as[ c ];
			auto d = max( p, q ) - min( p, q );
			if( e <= d ) break;
			e = d;
			cs[ 1 ] = c;
		}
		
		// RとSの差が最小になる境界を探索
		if( cs[ 3 ] <= cs[ 2 ] ) cs[ 3 ] = cs[ 2 ] + 1;
		for( auto c = cs[ 3 ], e = long.max; c < cs[ 4 ]; c++ )
		{
			auto r = as[ c ] - as[ cs[ 2 ] ];
			auto s = as[ cs[ 4 ] ] - as[ c ];
			auto d = max( r, s ) - min( r, s );
			if( e <= d ) break;
			e = d;
			cs[ 3 ] = c;
		}
		
		// PQRSの最大値と最小値の差を計算
		auto p = as[ cs[ 1 ] ] - as[ cs[ 0 ] ];
		auto q = as[ cs[ 2 ] ] - as[ cs[ 1 ] ];
		auto r = as[ cs[ 3 ] ] - as[ cs[ 2 ] ];
		auto s = as[ cs[ 4 ] ] - as[ cs[ 3 ] ];
		ans = min( ans, max( p, q, r, s ) - min( p, q, r, s ) );
	}
	return ans;
}
