Bài toán 2: Market (Olympic Balkan 2000)

Phát biểu bài toán

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 nào đó.
Chẳng hạn: 4kg, 6kg, ...

Ví dụ: có 3 con cá, khối lượng lần lượt là 3, 2, 4.

• Mua lượng 6kg sẽ lấy con cá thứ 2 và thứ 3.
• Mua lượng 3kg thì lấy con thứ nhất.
• Không thể mua lượng 8kg.

Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?

Input

Dữ liệu vào từ file văn bản market.inp:

• Dòng 1: một số nguyên dương N duy nhất (n ≤ 10^5)
• Dòng 2: gồm N số nguyên dương a1, a2, ..., aN, cách nhau bởi dấu cách, là khối lượng của N con cá.

Output

Ghi ra file văn bản market.out:

• Một số nguyên duy nhất: số lượng khác nhau mà người mua đầu tiên có thể chọn.

Ví dụ

Input

3
2 3 4

Output

7

Giải thích

Các tổng khối lượng có thể chọn được từ các tập con khác rỗng của dãy 2, 3, 4 là:

• 2
• 3
• 4
• 2 + 3 = 5
• 2 + 4 = 6
• 3 + 4 = 7
• 2 + 3 + 4 = 9

Có tất cả 7 lượng khác nhau.