Smallest Positive Missing Sum

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

Formally, let \( S = \{ \sum_{i \in I} a_i \mid I \subseteq \{1, 2, \ldots, n\} \} \) be the set of all subset sums (where the empty subset yields a sum of 0). You need to find the smallest positive integer \( x \) such that \( x \notin S \).

Example: For the array [1, 2, 3], the subset sums are \(\{1, 2, 3, 1+2, 1+3, 2+3, 1+2+3\} = \{1, 2, 3, 3, 4, 5, 6\}\). Thus, the smallest missing positive integer is 7.

inputFormat

The input is given in the following format:

n
a1 a2 a3 ... an

Where:

• n (1 ≤ n ≤ 10⁵) is the number of elements in the array.
• a1, a2, ..., an are the positive integers.

outputFormat

Output a single integer — the smallest positive integer that cannot be formed as the sum of any subset of the array.

3
1 2 3

7