"Gương mặt thân quen" là một chương trình giải trí khá nổi tiếng trên VTV3. Trong chương trình này, mỗi thí sinh sẽ bắt chước giọng hát của một ca sĩ nổi tiếng nào đó và trên cơ sở đó, ban giám khảo sẽ cho điểm từng thí sinh.
Có tất cả $n$ thí sinh tham gia thi. Cuộc thi được diễn ra trong nhiều vòng thi khác nhau. Mỗi vòng thi, thí sinh tốt nhất sẽ được $n$ điểm, thí sinh tốt thứ nhì được $n - 1$ điểm, thí sinh tốt thứ ba được $n - 2$ điểm, $\ldots$, thí sinh tốt thứ $n$ được $1$ điểm. Điểm của mỗi vòng thi của từng thí sinh được cộng lại, sau vòng thi cuối cùng thí sinh nào được nhiều điểm nhất sẽ giành chức vô địch. Tất nhiên, nếu có nhiều thí sinh cùng đạt nhiều điểm nhất thì tất cả họ đều giành chức vô địch. Chỉ còn một vòng thi nữa là cuộc thi kết thúc. Hiện tại điểm tổng của các thí sinh là $a_1, a_2, \ldots, a_n$. Hỏi rằng có bao nhiêu thí sinh có quyền hy vọng rằng mình sẽ đạt chức vô địch sau vòng thi cuối cùng?

Input:

• dòng đầu tiên gồm một số nguyên dương $n$ là số lượng thí sinh tham gia dự thi.
• $n$ dòng tiếp theo, mỗi dòng gồm một số nguyên dương $a_i$ $(0 \leq a_i \leq 2 \times 10 ^ {6})$ là số điểm của các thí sinh trước vòng thi cuối cùng.

Output:

• Gồm một dòng là số lượng thí sinh có thể đạt được chức vô địch sau vòng thi cuối cùng.

Subtasks:

• Subtask $1$ ($50$%): $2 < n \leq 100$
• Subtask $2$ ($50$%): $100 < n \leq 3 \times 10 ^ {5}$

Example

5
15
14
15
12
14

4

3
8
10
9

3