import numpy as np
N=int(input())
A=list(map(int, input().split()))
A=np.array(A)

sum_ = 0
left = 0
right = 0
for i in range(N):
  seq1 = A*(np.arange(N)-left)
  seq2 = A*(np.arange(N)[::-1]-right)
  if max(seq1) >= max(seq2):
    sum_ += max(seq1)
    A[seq1.argmax()]=0
    left += 1
  else:
    sum_ += max(seq2)
    A[seq2.argmax()]=0
    right += 1

print(sum_)