n = gets.to_s.to_i
a = gets.to_s.split.map{|t| t.to_i }

a = a.map.with_index{|t,i| [t,i] }

dp = Array.new(n+1){ [0] * (n+1) }

a.each_with_index do |tmp,i|
  a = tmp[0]
  k = tmp[1]
  (i+1).times do |j|
    
    dp[i+1][j+1] = [ dp[i+1][j+1],  dp[i][j] + (k-j) * a       ].max
    dp[i+1][j]   = [ dp[i+1][j],    dp[i][j] + (n-i+j-1-k) * a ].max
  end
end

puts dp[-1].max