quit() = exit(0)
in_1() = parse(Int, readline())
in_a() = parse.(Int, split(readline()))

function main()
  N = in_1()
  A = in_a()
  @assert length(A) == N
  after = zeros(Int, N)
  done = fill(false, N)
  score = 0
  for (pos, a) in sort(collect(enumerate(A)), by=last, rev=true)
    to1 = findfirst(i->iszero(after[i]), 1:pos)
    to2_0 = findfirst(i->iszero(after[i]), N:-1:pos)
    if isnothing(to1)
      to2 = N - to2_0 + 1
      after[to2] = pos
      done[pos] = true
      score += a * (to2 - pos)
      continue
    elseif isnothing(to2_0)
      after[to1] = pos
      done[pos] = true
      score += a * (pos - to1)
      continue
    end
    to2 = N - to2_0 + 1
    sc0_1, sc0_2 = pos - to1, to2 - pos
    sc1_1 = sum([A[i] for i in 1:pos-1 if !done[i]])
    sc1_2 = sum([A[i] for i in pos+1:N if !done[i]])
    if sc0_1 + sc1_1 > sc0_2 + sc1_2
      after[to1] = pos
      done[pos] = true
      score += a * sc0_1
    else
      after[to2] = pos
      done[pos] = true
      score += a * sc0_2
    end
  end
  println(score)
end

main()
