N = gets.to_i
A = gets.chomp.split.map(&:to_i)
left = 0
right = N-1

B = A.map.with_index { |elem, index| [index, elem]}
C = B.sort_by { |b| b[1] }.reverse
dpn = { [0,0] => 0 }
dpn1 = {}
# (1..N).each do |n|
#   dpn.each do |d|
    
#     # left
#     n_left = left + d[0][0]
#     if C[n-1][0] >= n_left
#       l = d[1] + C[n-1][1] * (C[n-1][0] - n_left)
#       if dpn1[[d[0][0]+1,d[0][1]]].nil?
#         dpn1[[d[0][0]+1,d[0][1]]] = l
#       else
#         dpn1[[d[0][0]+1,d[0][1]]] = [l, dpn1[[d[0][0]+1,d[0][1]]]].max
#       end
#     end
    
#     # right
#     n_right = right - d[0][1]
#     if C[n-1][0] <= n_right
#       r = d[1] + C[n-1][1] * (C[n-1][0] - n_right).abs
#       if  dpn1[[d[0][0],d[0][1]+1]].nil?
#         dpn1[[d[0][0],d[0][1]+1]] = r
#       else
#         dpn1[[d[0][0],d[0][1]+1]] = [r, dpn1[[d[0][0],d[0][1]+1]]].max
#       end
#     end
#   end
#   dpn = dpn1
#   p dpn
#   dpn1 = {}
# end
p dpn.max { |x, y| x[1] <=> y[1] }[1]