unittest
{
	assert( [ "4", "1 3 4 2" ].parse.expand.solve == 20 );
	assert( [ "6", "5 5 6 1 1 1" ].parse.expand.solve == 58 );
	assert( [ "6", "8 6 9 1 2 1" ].parse.expand.solve == 85 );
}



import std.container;
import std.conv;
import std.math;
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 )
{
	auto ans = 0L;
	auto l = 0L;
	auto r = as.length.signed - 1;
	auto fs = new bool[ as.length ];
	auto rbt_l = redBlackTree!( Tuple!( long, size_t ) )();
	auto rbt_r = redBlackTree!( Tuple!( long, size_t ) )();
	while( l <= r )
	{
		if( rbt_l.empty )
		{
			foreach( i, a; as )
			{
				if( !fs[ i ] ) rbt_l.insert( tuple( a * abs( i.signed - l ), i ) );
			}
		}
		if( rbt_r.empty )
		{
			foreach( i, a; as )
			{
				if( !fs[ i ] ) rbt_r.insert( tuple( a * abs( i.signed - r ), i ) );
			}
		}
		
		if( rbt_l.back[ 0 ] < rbt_r.back[ 0 ] )
		{
			auto i = rbt_r.back[ 1 ];
			ans += rbt_r.back[ 0 ];
			fs[ i ] = true;
			r--;
			rbt_r.clear();
			rbt_l.removeKey( tuple( as[ i ] * abs( i.signed - l ), i ) );
		}
		else if( rbt_r.back[ 0 ] < rbt_l.back[ 0 ] )
		{
			auto i = rbt_l.back[ 1 ];
			ans += rbt_l.back[ 0 ];
			fs[ i ] = true;
			l++;
			rbt_l.clear();
			rbt_r.removeKey( tuple( as[ i ] * abs( i.signed - r ), i ) );
		}
		else
		{
			if( as[ rbt_l.back[ 1 ] ] < as[ rbt_r.back[ 1 ] ] )
			{
				auto i = rbt_r.back[ 1 ];
				ans += rbt_r.back[ 0 ];
				fs[ i ] = true;
				r--;
				rbt_r.clear();
				rbt_l.removeKey( tuple( as[ i ] * abs( i.signed - l ), i ) );
			}
			else
			{
				auto i = rbt_l.back[ 1 ];
				ans += rbt_l.back[ 0 ];
				fs[ i ] = true;
				l++;
				rbt_l.clear();
				rbt_r.removeKey( tuple( as[ i ] * abs( i.signed - r ), i ) );
			}
		}
	}
	return ans;
}
