Problem Description

You have a balance scale and $N$ weights. The weights have masses $W_{1}, W_{2}, \cdots, W_{N}$ in order. Please compute how many different weights can be measured in total.

Note that the weights can be placed on both sides of the balance.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$.

Output Format

Output one integer representing the answer.

3
1 4 6

10

Hint

[Sample Explanation]

The 10 measurable weights are: $1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11$.

$$\begin{aligned} &1=1 \\ &2=6-4(\text { place } 6 \text { on one side of the balance, and } 4 \text { on the other side) } \\ &3=4-1 \\ &4=4 \\ &5=6-1 \\ &6=6 \\ &7=1+6 \\ &9=4+6-1 \\ &10=4+6 \\ &11=1+4+6 \end{aligned}$$

[Scale and Constraints for Test Cases]

For $50 \%$ of the test cases, $1 \leq N \leq 15$.

For all test cases, $1 \leq N \leq 100$, and the total weight of the $N$ weights does not exceed $10^5$.

Lanqiao Cup 2021 First Round Provincial Contest, Group A Problem F (Group B Problem G).

Translated by ChatGPT 5