说明

蒟蒻队长最近打算办一场最强大脑比拼！

他决定用最传统的答题模式来比拼，每次蒟蒻队长会提出一个问题，比拼双方如果有人回答不出问题则判失败

现在蒟蒻队长邀请了 $n$ 位同学来参加比拼，为了方便理解，蒟蒻队长将每位同学的实力进行了数字化

对于第 $i$ 位同学来说，蒟蒻队长认为他的实力可以转化成答题量 $a_i$，也就是说这位同学的实力支持他最多回答出 $a_i$ 道题

当比拼双方有人的答题量变为 $0$ 的时候则判定失败，获胜者会留在台上和下一位同学继续比拼，如果双方同时失败则认为获胜者的剩余答题量为 $0$，接下来上台的同学不需要和他比拼直接获得胜利

现在蒟蒻队长可以随意安排所有人的上台比拼顺序，为了让这次比拼有看头，他想知道怎么安排比拼顺序可以使得最后留在台上的获胜者的剩余答题量尽可能小？

比如有 $7$ 位同学，答题量分别为 $5,4,9,3,4,6$

蒟蒻队长可以安排比拼顺序为 $9,5,4,6,3,4,0$

第一次比拼为 $(9,5)$，获胜者剩余答题量为 $4$，和下一位同学继续比拼
第二次比拼为 $(4,4)$，双方同时失败，获胜者剩余答题量为 $0$，下一位同学 $6$ 上台直接获胜
第三次比拼为 $(6,3)$，获胜者剩余答题量为 $3$，和下一位同学继续比拼
第三次比拼为 $(3,4)$，获胜者剩余答题量为 $1$
第四次比拼为 $(1,0)$，因为最后一位同学的答题量为 $0$，所以不需要比拼，上台即失败，获胜者剩余答题量为 $1$

输入格式

第一行一个整数 $n$ 表示同学人数

接下来一行包含 $n$ 个整数，分别表示每位同学的答题量

测试点编号	特殊性质
$1 \sim 2$	$a_i=0/1$
$3 \sim 5$	$a_i=i$
$6 \sim 8$	$n \leq 15$
$9 \sim 10$	无

对于所有的数据，有 $1 \leq n \leq 100, a_i \geq 0, \sum{a_i} \leq 10^6$

</span>

输出格式

输出最后获胜者最小的剩余答题量

7
9 5 4 3 4 6 0

1

来源

CSP模拟赛