题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_{1}, W_{2}, \cdots, W_{N}$。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

对于 $50 \%$ 的评测用例, $1 \leq N \leq 15$。

对于所有评测用例, $1 \leq N \leq 100, N$ 个砝码总重不超过 $10^5$。

输入格式

输入的第一行包含一个整数 $N$。

第二行包含 $N$ 个整数: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$。

输出格式

输出一个整数代表答案。

样例

样例输入 1

3
1 4 6

样例输出 1

10

提示

样例说明： 能称出的 $10$ 种重量是: $1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11$。

$$\begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ &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}$$