Hai chuồng bò

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Sắn vừa xây hai chuồng bò mới và muốn nhốt bò vào hai chuồng sao cho tổng lượng sữa của các con bò trong chuồng thứ nhất bằng tổng lượng sữa của các con bò trong chuồng thứ hai. Mỗi con bò được nhốt vào tối đa một chuồng; những con bò không được nhốt vào chuồng nào coi như bị "thừa".

Sắn không muốn bỏ phí con bò nào nên muốn số con bò bị thừa là ít nhất. Hãy tính số con bò thừa tối thiểu. (Cho phép để trống cả hai chuồng, khi đó tổng của hai chuồng cùng bằng \(0\) và mọi con bò đều thừa.)

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên duy nhất là số con bò thừa tối thiểu.

Constraints

• \(1 \le n \le 15\)
• \(1 \le a_i \le 10^9\)

Sample Input

7
10 4 6 3 3 9 12

Sample Output

1

Explanation

Tổng lượng sữa là \(47\) (số lẻ) nên chắc chắn phải bỏ ra ít nhất một con. Bỏ con thứ \(6\) (\(9\) đơn vị) ta còn \(38\), chia được thành chuồng một gồm các con \(10, 3, 6\) và chuồng hai gồm \(12, 4, 3\) với cùng tổng \(19\).