问题描述

你有一架天平和$N$个砝码，这$N$个砝码重量依次是$W_1,W_2,\cdots W_N$。 请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数$N$。 第二行包含$N$个整数：$W_1, W_2, W_3, \cdots W_N$。

输出格式

输出一个整数代表答案。

样例输入输出

3
1 4 6

10

样例说明

能称出的10种重量是：1、2、3、4、5、6、7、9、10、11。

1 = 1；

2 = 6 - 4；（天平一边放6，另一边放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。

评测用例规模与规定

对于$50\%$的评测样例,$1 \leqslant N \leqslant 15$。

对于$100\%$的评测样例，$1 \leqslant N \leqslant 100$, $N$个砝码重量总重不超过100000。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$256M$