Smallest Unobtainable Sum

You are given an array of positive integers. Your task is to determine the smallest positive integer that cannot be represented as the sum of any subset of the given array. A subset is defined as a collection of elements that can be chosen from the array, regardless of their order.

Formally, let \(arr\) be an array of positive integers. Find the smallest positive integer \(S\) such that there is no subset \(A \subseteq arr\) with \(\sum_{a \in A} a = S\). For instance, if \(arr = [1, 2, 5]\), the possible subset sums can form all integers from 1 to 3, and the answer will be 4.

Note: The empty subset is considered with a sum of 0, but since we are looking for a positive integer, 0 is not taken into account.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated positive integers.

If \(n = 0\), then the array is empty.

outputFormat

Print a single integer to stdout representing the smallest positive integer that cannot be formed as a sum of any subset of the array.

3
1 2 5

4