Cặp song sinh (Twins)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ đồng xu với giá trị $a_i$. Bạn muốn lấy ít đồng xu nhất sao cho tổng giá trị phần mình lấy lớn hơn nghiêm ngặt tổng giá trị các đồng còn lại. Hãy tìm số đồng xu tối thiểu.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số $a_i$.

Output

In số đồng xu tối thiểu cần lấy.

Subtask

Các giới hạn chung:

• $1 \le n \le 100$.

• $1 \le a_i \le 100$.

• Subtask 1 (20 điểm): $n \le 10$

• Subtask 2 (30 điểm): $n \le 50$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

3
2 1 2

Output

2

Giải thích

Lấy hai đồng giá trị $2$ được tổng $4$, lớn hơn đồng còn lại có tổng $1$. Một đồng bất kỳ chưa đủ.