Smallest Positive Integer Not Representable as Subset Sum

You are given an array of positive integers. Your task is to find the smallest positive integer that cannot be represented as the sum of a subset of the array.

More formally, given an array \(a_1, a_2, \dots, a_n\), find the smallest positive integer \(X\) such that no subset of the array has a sum equal to \(X\). A subset can be empty (which sums to 0) or any combination of the elements.

Hint: Sort the array. Initialize \(X=1\) and update it while traversing the sorted array. If an element is greater than \(X\), then \(X\) is the answer; otherwise, add the element to \(X\).

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a single integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated positive integers.

Example:

3
1 2 3

outputFormat

Print to standard output (stdout) a single integer, which is the smallest positive integer that cannot be represented as the sum of any subset of the given array.

Example:

7

## sample

3
1 2 3

7