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



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

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

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	
	// 各部分列の最大総和が最小になるように二分探索
	auto x = bisect!( ( long x )
	{
		auto ts = new long[ 4 ];
		auto ti = 0L;
		foreach( i, a; as )
		{
			if( 0 < ts[ ti ] && ( x < ts[ ti ] + a || as.length.signed - i.signed < ts.length.signed - ti ) ) ti++;
			if( ts.length <= ti ) return false;
			ts[ ti ] += a;
		}
		return true;
	}
	)( 0L, as.sum );
	
	// 各部分列の最大総和と最小総和の差を計算
	auto ts = new long[ 4 ];
	auto ti = 0L;
	foreach( i, a; as )
	{
		if( 0 < ts[ ti ] && ( x < ts[ ti ] + a || as.length.signed - i.signed < ts.length.signed - ti ) ) ti++;
		ts[ ti ] += a;
	}
	auto ms = reduce!( min, max )( tuple( long.max, 0L ), ts );
	return ms[ 1 ] - ms[ 0 ];
}

// 単調増加or減少関数の二分探索
auto bisect( alias pred )( long ng, long ok )
if( is( typeof( pred( ng ) ) : bool ) )
{
	while( 1 < abs( ok - ng ) )
	{
		auto x = ( ok + ng ) / 2;
		if( pred( x ) ) ok = x;
		else            ng = x;
	}
	return ok;
}
