import java.lang.Math.abs

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

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

    data class Problem(val items: List<Infant>, val minPos: Int, val maxPos: Int) {
        fun getOneChoice(): Long? {
            return when {
                items.isEmpty() -> 0L
                else -> null
            }
        }

        override fun toString(): String {
            return "$minPos|${
            items.sortedBy { it.pos }.joinToString(" ") { it.value.toString() }
            }|$maxPos"
        }
    }


    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> { problem ->
            problem.getOneChoice() ?: problem.let {
                val infant = it.items.first()
                // generate subProblem
                val left = Problem(
                    items = it.items.drop(1),
                    minPos = it.minPos + 1,
                    maxPos = it.maxPos
                )
                val right = Problem(
                    items = it.items.drop(1),
                    minPos = it.minPos,
                    maxPos = it.maxPos - 1
                )

                // generate choices
                val leftValue = get(left) + infant.value * abs(infant.pos - it.minPos)
                val rightValue = get(right) + infant.value * abs(it.maxPos - infant.pos)

                // evaluate choices
                val value = if (leftValue < rightValue) rightValue else leftValue
                //log("$it = $value")
                value
            }
        }
        val ans = table[Problem(items = items, minPos = 0, maxPos = N - 1)]
        println(ans)
    }


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

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

    class LazyMap<K, V>(private val init: LazyMap<K, V>.(K) -> V) : Map<K, V> {
        private val memo = HashMap<K, V>()
        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()
    }
}