班级内共有 n 个人，你知道每个人体重 a_i。

现在我们要从 n 个人中挑选若干个人分成两队进行拔河比赛，分别为 A 队和 B 队。

请问 A 队和 B 队有可能的体重差的绝对值有多少种？

A 队和 B 队允许其中一个队伍为 0 个人，但不能同时为 0 个人。

第一行单个整数表示 n。

第二行 n 个整数表示 w_1, w_2, \ldots, w_n，为每个人的体重。

输出一行一个整数，表示两个队伍体重差绝对值的种数。

样例 1 解释

三个人体重为 1, 4, 10，可以得到的差值有：

1, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15，共 12 种。

例如差 7：A 队取 1 + 10 = 11，B 队取 4；差 6：A 队取 10，B 队取 4。

数据范围

• 对于 50\% 的数据，1 \le n \le 15；
• 对于 100\% 的数据，1 \le n \le 100，1 \le w_i \le 10^5，w_1 + w_2 + \cdots + w_n \le 10^5。

提示

把「进 A 队」看成 +w_i、「进 B 队」看成 -w_i、「不去」看成 0，那么差值就是这些带符号和的绝对值。因为所有体重之和不超过 10^5，可以直接对差值做可行性 DP：f(d) 表示差 d 能否凑出来，每个人把 f 平移 w_i 和 -w_i 各更新一次。

注意一个细节：不能一个人都不选。所以 d = 0 不能靠「初始状态」白给，只能由真正选过人（例如两队各取一部分、和相等）凑出来。