Trong một vương quốc nọ, nhà vua đang sở hữu một bộ sưu tập gồm \(n\) viên ngọc quý, mỗi viên có một giá trị tâm linh riêng biệt. Để củng cố quyền lực của mình, nhà vua muốn chọn ra một nhóm gồm ít viên ngọc nhất có thể, sao cho tổng giá trị của nhóm ngọc này phải lớn hơn tổng giá trị của tất cả các viên ngọc còn lại trong bộ sưu tập.

Hãy giúp nhà vua xác định số lượng viên ngọc tối thiểu cần chọn để đạt được mục tiêu "cán cân quyền lực" này.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)) là số lượng viên ngọc.
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)) lần lượt là giá trị của từng viên ngọc.

Output

• Một số nguyên duy nhất là số lượng viên ngọc ít nhất cần chọn.

Example

4
3 1 7 1

1

3
2 1 2

2

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \le 10^5\).