Sau khi trồng cây xong, doanh nhân DeMen100ms lại làm thêm một công việc khác đó là nuôi bò.

Vì không muốn bị lỗ vốn, DeMen100ms chỉ mua về 15 con bò để nuôi. Nuôi một thời gian thì chuồng bò của DeMen100ms cũng xuống cấp. DeMen100ms xây lại hẳn hai cái chuồng bò để nuôi nhốt chúng. Việc bây giờ là chia các chú bò sữa vào hai chuồng sao cho sản lượng sữa của mỗi chuồng là bằng nhau. Và nếu chia như vậy thì có khả năng là sẽ thừa ra một số chú bò để các chú bò còn lại chia vào hai chuồng cho đều sản lượng sữa, Rõ ràng nếu một chú bò không thể chia vào một trong hai chuồng là điều đáng tiếc nên DeMen100ms muốn giảm thiểu điều này. Bạn hãy tính giúp cho DeMen100ms nếu chia tốt nhất thì số lượng bò tối thiểu không có chuồng là bao nhiêu chú.

Input

• Dòng thứ nhất là số nguyên dương \(n\).

• Dòng thứ hai là là \(n\) số nguyên dương \(a_1, a_2, ... a_n (1 \le a_i \le 10^9)\) là sản lượng sữa của n chú bò.

Output

• In ra một số nguyên duy nhất là số lượng bò tối thiểu không thể chia vào bất cứ chuồng nào dù cách chia tốt nhất.

Example

3
5 9 5

1

6
3 3 3 3 3 1

2