Problem1231--厨师PIPI

1231: 厨师PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 10
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI手上有n种食材,编号为i的食材有一个美味度ai。我们将这n种食材定义为一个集合S,S = (a1,a2, …, an), PIPI每次可以在集合S中取出一个子集S'做出一道美味度∑S'的菜肴,但是有一些美味度的菜肴PIPI是做不出来的,我们定义PIPI利用手上的食材,做不出来菜肴的最小美味度为mex(S):


PS: S'是S的一个子集, ∑S' 代表S'中所有元素的和. 若S'为空,则 ∑S' is 0.
现在给你一个集合S,请你帮PIPI计算出求出mex(S),好让PIPI去补充食材,做出更多美味的菜肴~

Input

输入第一行包含一个正整数n,代表食材的种类数。(1 ≤ n 1e5).
接下来有n个非负整数,代表食材的美味度。

Output

输出 mex(S)

Sample Input

3
1 2 5

Sample Output

4

HINT

S'=(), ∑S'=0

S'=(1), ∑S'=1

S'=(2), ∑S'=2

S'=(1,2), ∑S'=3

S'=(5), ∑S'=5
PIPI没办法做出美味度为 4 的菜肴,故mex(S) = 4

Source/Category

中等