Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là a_i, đem bán ngoài chợ. Ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng S nào đó (ví dụ 3 kg, 5 kg…). Khi chọn lượng S, người mua phải lấy một tập con các con cá sao cho tổng khối lượng đúng bằng S. Ví dụ: có 3 con cá với khối lượng 3, 2, 4. Mua lượng 6 kg sẽ lấy con thứ 2 và thứ 3; mua lượng 3 kg sẽ lấy con thứ nhất; không thể mua lượng 8 kg.

Yêu cầu: Nếu bạn là người đầu tiên mua cá, hãy tính có bao nhiêu giá trị S khác nhau có thể chọn (chỉ tính S > 0).

Input

Dòng 1 chứa số n (0 < n ≤ 100).

Dòng tiếp theo ghi n số a₁, a₂, …, a_n (0 ≤ a_i ≤ 100).

Output

Xuất số lượng giá trị S > 0 có thể tạo được.

Ví dụ

Input

5
1 9 3 4 7

Output

20

Input

3
1 2 3

Output

6