
object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  solve
  def solve: Unit ={
    val n = readLine.trim.toInt
    if (n == 0) return
    val powers = readLine.trim.split(' ').map(_.toLong)
    val sum = powers.sum
    val target = (powers.sum + 1) / 2
    val left = powers.take(n / 2).map(it ⇒ List(0L, it)).foldLeft(List(0L)){case (l, r) ⇒ l.flatMap(it ⇒ r.map(_ + it))}.sorted
    val right = powers.drop(n / 2).map(it ⇒ List(0L, it)).foldLeft(List(0L)){case (l, r) ⇒ l.flatMap(it ⇒ r.map(_ + it))}.sorted.toArray
    println(
      left.map{a ⇒
        lowerBound(right, target - a).let{it ⇒ if (right.indices.contains(it)) right(it) else right.last} + a
      }.map{it ⇒ math.abs(sum - it - it)}.min
    )

    solve
  }
  def upperBound[T <: Ordered[T]](array: Array[T], target: T): Int = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) <= target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  def lowerBound[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Int = {
    var left = 0
    var right = array.length
    while (left < right){
      val mid = (left + right) / 2
      if (ordering.compare(array(mid), target) < 0){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  def lowerBound[T <: Ordered[T]](array: Array[T], target: T): Int = {
    var left = 0
    var right = array.length
    while (left < right){
      val mid = (left + right) / 2
      if (array(mid) < target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }

  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}
