Smallest Unrepresentable Sum

You are given an integer N and an array of N 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.

For example, if the array is [1, 2, 3, 8, 9, 10], the smallest integer that is missing from any possible subset sum is 7 (since we can form 1, 2, 3, 4, 5, 6, 8, ... but not 7).

The problem can be solved using a greedy strategy. After sorting the array, maintain a variable smallest_missing which starts at 1. Iterate through the array and if the current number is greater than smallest_missing, then smallest_missing is the number we are looking for. Otherwise, add the current number to smallest_missing and continue.

Input Format: The first line contains an integer N, representing the number of elements in the array. The second line contains N space-separated integers.

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

The key idea is to gradually build up the range of representable sums, and once a gap is encountered, that gap is the answer.

inputFormat

The input is provided via stdin and consists of two lines:

• The first line contains a single integer N (1 ≤ N ≤ 10⁵), the number of elements in the array.
• The second line contains N space-separated positive integers.

outputFormat

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

## sample

6
1 2 3 8 9 10

7

</p>