module module_sort
    implicit none
    interface sort
        module procedure int_heap_sort, real_heap_sort
    end interface

    contains

        subroutine int_heap_down(a,node,las)
            implicit none
            integer(8) a(*),x
            integer(8) node,par,ch1,ch2,las
            par = node
            x = a(par); ch1 = par*2
            do while(ch1 <= las)
                ch2 = ch1+1
                if(ch2 <= las .and. a(ch1) < a(ch2)) ch1 = ch2
                if(a(ch1) > x) then
                    a(par) = a(ch1); a(ch1) = x
                else 
                    exit
                end if
                par = ch1; ch1 = par*2
            end do
        end subroutine int_heap_down

        subroutine int_heap_sort(a,n)
            implicit none
            integer(8) a(*),x
            integer(8) n,i
            do i = n/2, 1, -1
                call int_heap_down(a,i,n)
            end do
            do i=n,2,-1
                x = a(i); a(i) = a(1); a(1) = x
                call int_heap_down(a,1_8,i-1)
            end do
        end subroutine int_heap_sort

        subroutine real_heap_down(a,node,las)
            implicit none
            real a(*), x
            integer(8) node,par,ch1,ch2,las
            par = node
            x = a(par); ch1 = par*2
            do while(ch1 <= las)
                ch2 = ch1+1
                if(ch2 <= las .and. a(ch1) < a(ch2)) ch1 = ch2
                if(a(ch1) > x) then
                    a(par) = a(ch1); a(ch1) = x
                else 
                    exit
                end if
                par = ch1; ch1 = par*2
            end do
        end subroutine real_heap_down

        subroutine real_heap_sort(a,n)
            implicit none
            real a(*),x
            integer(8) n,i
            do i = n/2, 1, -1
                call real_heap_down(a,i,n)
            end do
            do i=n,2,-1
                x = a(i); a(i) = a(1); a(1) = x
                call real_heap_down(a,1_8,i-1)
            end do
        end subroutine real_heap_sort

end module module_sort

program ActiveInfants
    use module_sort
    implicit none
    integer(8) :: N,A(3000),B(3000),dp(0:3000,0:3000) = -1,shift = 100000,nowA,nowidx,ans = -1
    integer(8) :: i,j

    read *,N,A(1:N)

    do i = 1, N
        B(i) = A(i)*shift+i
    end do 

    call sort(B,N)
    B(1:N) = B(N:1:-1)

    dp(0,0) = 0

    do i = 0, N
        do j = 0, N
            !print *,i,j,dp(i,j)
            if(i+j == N) ans = max(dp(i,j),ans)
            if(i+j >= N) cycle
            nowA = B(i+j+1)/shift
            nowidx = mod(B(i+j+1),shift)
            dp(i+1,j) = max(dp(i+1,j),dp(i,j)+nowA*abs(nowidx-(i+1)))
            dp(i,j+1) = max(dp(i,j+1),dp(i,j)+nowA*abs(nowidx-(N-j)))
        end do
    end do

    print '(i0)', ans

end program ActiveInfants