Smallest Impossible Total

You are given a machine with n buttons. Each button has an associated positive integer value. When a button is pressed, its value is added to the total sum. However, each button can be pressed at most once. In other words, you are given a set of numbers and you can form different totals by summing some or all of these numbers (each used at most once).

Your task is to determine the smallest positive integer \(T\) that cannot be obtained as the sum of a subset of the given button values.

Hint: If you sort the button values in increasing order, you can use a greedy strategy to determine \(T\). Start with \(T = 1\) and for each button value \(a_i\), if \(a_i \leq T\) then update \(T = T + a_i\); otherwise, \(T\) is the answer.

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq 10^5)\) — the number of buttons.

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\) representing the values of each button.

Input is given via standard input (stdin).

outputFormat

Print a single integer, the smallest positive integer \(T\) that cannot be obtained as the sum of any subset of the given button values. The answer should be printed to standard output (stdout).

3
1 2 3

7