import java.lang.Math.abs
import kotlin.math.max

fun main(args: Array<String>) = ABC163E.main()

object ABC163E {
    var equalCount = 0
    var hashCount = 0

    fun log(message: Any?) {
        //println(message)// TODO: ←消す
    }

    data class Problem(val remains: List<Infant>, val lefts: Set<Infant>, val rights: Set<Infant>) {
        val minPos: Int get() = lefts.size
        val maxPos: Int get() = lefts.size + remains.size - 1
        fun getOneChoice(): Long? {
            return when {
                remains.isEmpty() -> 0L
                else -> null
            }
        }

        override fun toString(): String {
            return "${lefts.joinToString(" ") { it.value.toString() }}|${
            remains.sortedBy { it.pos }.joinToString(" ") { it.value.toString() }
            }|${rights.reversed().joinToString(" ") { it.value.toString() }}"
        }

        override fun equals(other: Any?): Boolean {
            equalCount++
            return super.equals(other)
        }

        override fun hashCode(): Int {
            hashCount++
            var result = remains.size
            result = 31 * result + lefts.size
            result = 31 * result + rights.size
            return result
        }
    }


    fun main() {
        val N = readInt()
        val A = readLongs()

        val items = A.mapIndexed { index, it -> Infant(pos = index, value = it) }
            .sortedByDescending { it.value }
        //log(items.joinToString("\n"))

        val table = LazyMap<Problem, Long>(N * N) {
            it.getOneChoice() ?: it.let {
                val infant = it.remains.first()
                val remainInfant = it.remains.drop(1)

                val leftDv = infant.value * abs(infant.pos - it.minPos)
                val rightDv = infant.value * abs(it.maxPos - infant.pos)

                val rightProblem = Problem(remainInfant, lefts = it.lefts, rights = it.rights + infant)
                val leftProblem = Problem(remainInfant, lefts = it.lefts + infant, rights = it.rights)
                when {
                    leftDv < rightDv -> get(rightProblem) + rightDv
                    leftDv > rightDv -> get(leftProblem) + leftDv
                    else -> max(get(rightProblem), get(leftProblem)) + rightDv
                }
            }
        }
        val ans = table[Problem(remains = items, lefts = emptySet(), rights = emptySet())]
        println(ans)
        log("equalCount=$equalCount")
        log("hashCount=$hashCount")
        log("tableSize=${table.size}")
    }


    /*####################################################################################*/
    data class Infant(val pos: Int, val value: Long)

    fun readInt() = readLine()!!.toInt()
    fun readLongs() = readLine()!!.split(" ").map { it.toLong() }

    class LazyMap<K, V>(capacity: Int, private val init: LazyMap<K, V>.(K) -> V) : Map<K, V> {
        private val memo = HashMap<K, V>(capacity)
        override fun get(key: K): V {
            return memo[key] ?: init(key).memorizingAt(key)
        }


        private fun V.memorizingAt(key: K): V {
            memo[key] = this
            return this
        }

        override val entries: Set<Map.Entry<K, V>>
            get() = memo.entries
        override val keys: Set<K>
            get() = memo.keys
        override val size: Int
            get() = memo.size
        override val values: Collection<V>
            get() = memo.values

        override fun containsKey(key: K): Boolean = memo.containsKey(key)
        override fun containsValue(value: V): Boolean = memo.containsValue(value)
        override fun isEmpty(): Boolean = memo.isEmpty()
    }
}