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.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 )
{
	// dp[ 左からl番目まで確定済 ][ 右からr番目まで確定済 ] = うれしさの合計
	auto dp = new long[][]( 1 + as.length, 1 + as.length );
	foreach( i, a, p; zip( as, iota( as.length.signed ) ).array.sort!( ( x, y ) => y < x ).enumerate( 0L ) )
	{
		for( auto l = 0L, r = i; 0 <= r; l++, r-- )
		{
			dp[ l + 1 ][ r ] = max( dp[ l + 1 ][ r ], dp[ l ][ r ] + a * ( p - l ) );
			dp[ l ][ r + 1 ] = max( dp[ l ][ r + 1 ], dp[ l ][ r ] + a * ( as.length.signed - 1 - r - p ) );
		}
	}
	
	auto ans = 0L;
	foreach( i; 0L .. dp.length.signed )
	{
		ans = max( ans, dp[ i ][ i ] );
	}
	return ans;
}
