N=int(input())
A=[]
for i,a in enumerate(map(int,input().split())):
  A.append([a,i])
A=sorted(A,key=lambda x:x[0], reverse=True)
r,l=0,N-1
ans=0
i=0
while r<=l:
  _=[A[i]]
  i+=1
  while i<N and A[i][0]==_[0][0]:
    _.append(A[i])
    i+=1
  _=sorted(_,key=lambda x:x[1],reverse=True)
  k=-1
  for _k in range(len(_)):
    if k==-1:
      k=0
    else:
      k=len(_)-1-k
      if k<len(_)//2:
        k+=1    
    a,j=_[k]
    if (l+r)/2<j:
      ans+=a*(j-r)
      r+=1
    else:
      ans+=a*(l-j)
      l-=1
print(ans)

