program test

integer(8) :: n,a(3000),b(3000),i,j,k,dp(0:3000,0:3000)=0,left,right,total,max_dp

read(*,*) n
read(*,*) (a(i),i=1,n)
do i=1,n
  b(i) = i
enddo

call heapsort_down(n,a(1:n),b(1:n))

! aが活発度、bが幼児の初期位置(x)
do total=1,n
  do left=0,total-1
    right=total-1-left    
    !左詰め
    dp(left+1,right) = max(dp(left+1,right),dp(left,right)+a(total)*abs(b(total)-(left+1)))
    !右詰め
    dp(left,right+1) = max(dp(left,right+1),dp(left,right)+a(total)*abs(b(total)-(n-right)))
  enddo
enddo

max_dp = 0
do left=0,n
  max_dp = max(max_dp,dp(left,n-left))
enddo

write(*,*) max_dp

contains
subroutine heapsort_down(n,y1,y2)

  implicit none
  integer(8),intent(in) :: n
  integer(8),intent(inout) :: y1(1:n)
  integer(8),intent(inout) :: y2(1:n)
  integer(8) :: i,k,j,l
  integer(8) :: t1,t2
  
  l = n/2+1
  k = n

  do while (k /= 1)
     if(l > 1) then
        l = l-1
        t1 = y1(l)
        t2 = y2(l)
        
     else
        t1 = y1(k)
        t2 = y2(k)
        y1(k) = y1(1)
        y2(k) = y2(1)
        k = k-1
        if(k == 1) then
           y1(1) = t1
           y2(1) = t2
           exit
        endif
     endif

     i = l
     j = l+l

     do while(j <= k)
        if(j < k) then
           if(y1(j) > y1(j+1)) j = j+1
        endif
        
        if (t1 > y1(j)) then
           y1(i) = y1(j)
           y2(i) = y2(j)
           i = j
           j = j+j
        else
           j = k+1
        endif
     
     enddo
     
     y1(i) = t1
     y2(i) = t2
  
  enddo
  return

end subroutine heapsort_down



end program