import java.lang.Math.abs

fun main() = ABC163E2.main()

object ABC163E2 {
    var equalCount = 0
    var hashCount = 0
    var calcCount = 0

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

    val N: Int
    val infants: List<Infant>

    init {
        N = readInt()
        val A = readLongs()

        infants = A.mapIndexed { index, it -> Infant(pos = index, value = it) }
            .sortedBy { -it.value * A.size + it.pos }   // 価値=降順, 位置=昇順
    }

    data class Problem(
        val left: Int,  // 左に移動させた人数
        val right: Int  // 右に移動させた人数
    ) {
        val done get() = left + right   // 既に移動させた人数
        val remain get() = infants.size - done    // 残り人数
        val nextInfant get() = infants.getOrNull(done)
        val leftMoveValue: Long?
            get() = nextInfant?.let {
                it.value * abs(it.pos - left)
            }
        val rightMoveValue: Long?
            get() = nextInfant?.let {
                it.value * abs(infants.size - 1 - right - it.pos)
            }

        fun getOneChoiceOrNull(): Long? {
            return when {
                done == 0 -> 0L
                else -> null
            }
        }

        override fun equals(other: Any?): Boolean {
            equalCount++
            if (this === other) return true
            if (javaClass != other?.javaClass) return false

            other as Problem

            if (left != other.left) return false
            if (right != other.right) return false

            return true
        }

        override fun hashCode(): Int {
            hashCount++
            return left + right * N
        }
    }

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

    fun main() {
        val table = LazyMap<Problem, Long>(capacity = N * N) { problem ->
            calcCount++
            //log(problem)
            problem.getOneChoiceOrNull() ?: problem.let {
                // subproblems
                val subProblems = listOf(
                    Problem(left = it.left - 1, right = it.right),
                    Problem(left = it.left, right = it.right - 1)
                ).filter { it.left >= 0 && it.right >= 0 }
                // this value
                val value = subProblems.map { sub ->
                    get(sub) + if (sub.left < it.left) sub.leftMoveValue!! else sub.rightMoveValue!!
                }.max()!!
                value
            }
        }


        (0..infants.size).forEach { left ->
            val rightMax = infants.size - left
            (0..rightMax).forEach { right ->
                //log("prepare($left,$right)")
                table[Problem(left, right)]
            }
        }

        val candidateProblems = (0..infants.size).map { Problem(left = it, right = infants.size - it) }
        val candidates = candidateProblems.map {
            log("candidate=$it")
            table[it]
        }
        val ans = candidates.max()!!
        println(ans)
        log("calc=$calcCount")
        log("hash=$hashCount")
        log("equals=$equalCount")
    }


    /*####################################################################################*/

    fun readInt() = readLine()!!.toInt()
    fun readLongs() = readLine()!!.split(" ").map { it.toLong() }
    fun <E> List<E>.dropAt(index: Int): List<E> {
        val buf = this.toMutableList()
        buf.removeAt(index)
        return buf
    }

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

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

Measured memory_bytes: 316120