Smallest Missing Subset Sum

You are given an array of n positive integers. Your task is to compute the smallest positive integer \(x\) such that no subset of the given array sums exactly to \(x\). In other words, find the minimum \(x > 0\) for which there is no subset \(S \subseteq arr\) with \(\sum_{a \in S} a = x\).

For example, consider the array [1, 2, 3, 8]. The subset sums that can be formed are: \(1, 2, 3, 1+2=3, 1+3=4, 2+3=5, 1+2+3=6\), and then there is a gap at \(7\). Thus, the answer is 7.

The problem can be formally stated as follows: Given an array \(arr\) of positive integers, find the smallest positive integer \(x\) such that for every subset \(S \subseteq arr\), \(\sum_{a \in S} a \neq x\).

inputFormat

The first line of input contains an integer n (\(1 \leq n \leq 10^5\)) representing the number of elements in the array. The second line contains n space-separated positive integers.

outputFormat

Output a single integer, which is the smallest positive integer that cannot be represented as the sum of any subset of the array.

## sample

4
1 2 3 8

7

</p>