Distinct Dollar Amounts

You are given a collection of gifts, each with a specific price. Your task is to determine the number of distinct dollar amounts that can be formed by summing the prices of any subset of these gifts. Note that the empty subset, which yields a sum of 0, is also considered.

Formally, given \(n\) gifts with prices \(p_1, p_2, \ldots, p_n\), you need to compute the size of the set \[ \{ \sum_{i \in S} p_i : S \subseteq \{1,2,\ldots,n\} \}\n\], that is, the number of distinct sums you can obtain.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains a single integer \(n\) which represents the number of gifts.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the prices of the gifts.

outputFormat

Print a single integer to standard output (stdout) representing the number of distinct dollar amounts that can be formed using any subset of the given gifts.

4
3 4 2 1

11