Background

你有一架天平和N个砝码，这N个砝码重量依次是W1,W2,W3,…… WN，请你计算一共可以称出多少种不同的重量?

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

Input

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

第二行包含N个整数:W1,W2,W3,……, WN

Output

输出一个整数代表答案。

Samples

3
1 4 6

10

Limitation

能称出的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。

对于所有评测用例,1≤N≤15，N个砝码总重不超过100000.