
fun canMakePeaces(l: Int, minLimit:Int, maxLimit:Int, peaceSizes:Array<IntArray>, memo: Array<Boolean?>): Boolean {
    return when{
        l >= memo.size -> true
        memo[l] != null -> memo[l]!!
        else -> {
            var i = l
            while (i < memo.size && peaceSizes[l][i - l] < minLimit) ++i
            memo[l] = if (i == memo.size) false
            else {
                var res = false
                while (i < memo.size && peaceSizes[l][i - l] <= maxLimit && !res){
                    res = canMakePeaces(++i, minLimit, maxLimit, peaceSizes, memo)
                }
                (i - l < memo.size) && res
            }
            memo[l]!!
        }
    }
}
fun minDiff(minLimit: Int, peaceSizes: Array<IntArray>, memo: Array<Boolean?>, currentMin: Int = Int.MAX_VALUE): Int {
    var left = minLimit
    var right = if (currentMin != Int.MAX_VALUE) minLimit + currentMin else peaceSizes[0].last()
    while (left < right){
        val mid = (left + right) / 2
        memo.fill(null)
        if (canMakePeaces(0, minLimit, mid, peaceSizes, memo)) {
            right = mid
        }else {
            left = mid + 1
        }
    }
    return right - minLimit
}
fun main(args:Array<String>){
    val n = readLine()!!.toInt()
    val lines = IntArray(n){readLine()!!.toInt()}
    val peaceSizes = Array(n){l -> IntArray(n - l){r -> lines[l + r]}.also{
        for (i in 1 until it.size){
            it[i] += it[i - 1]
        }
    }}
    val memo = Array(n){null as Boolean?}
    var min = Int.MAX_VALUE
    for (i in 0 until n) for (j in i until n){
        if (i != 0 || j != n - 1) {
            val temp = minDiff(peaceSizes[i][j - i], peaceSizes, memo, min)
            if (min > temp) min = temp
        }
    }
    println(min)
}
