You are given an array A of n non negative integers. You have to find maximum value of x such that numbers from 1 to x can be created by adding values of some sub sequence's.Look at example for clearity: A = [1, 4, 11, 2, 9] 1 -> 1 2 -> 2 3 -> 1 + 2 4 -> 4 5 -> 4 + 1 6 -> 4 + 2 7 -> 1 + 4 + 2 there we can create numbers from 0 to 7 so answer is 7 Note: Output may not fit in a 32-bit signed integer
Input Format
a number n A[1] A[2] A[3] .... A[n]
Output Format
print single integer x
Constraints
1. 1 <= n <= 2 * 10^6 2. 1 <= A[i] <= 10^5
Notice
.
Example
Input
5 1 4 11 2 9
Output
7