B - 合格ラインの日々 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間にわたる試験期間を過ごしています。毎日 1 つの試験があり、i 日目 (1 \leq i \leq N) の試験における高橋君の点数は A_i 点です。

高橋君は毎日、試験が終わった後に、1 日目からその日までの全試験の平均点を計算します。その日の点数が平均点以上であれば、「今日は調子が良かった」と感じ、満足します。

具体的には、1 日目から k 日目までの平均点を

M_k = \frac{A_1 + A_2 + \dots + A_k}{k}

としたとき、A_k \geq M_k を満たす日 k に高橋君は満足します。これは k \cdot A_k \geq A_1 + A_2 + \dots + A_k と同値です。

なお、1 日目は平均点が A_1 自身となるため、高橋君は必ず満足します。

N 日間の試験の点数が与えられたとき、高橋君が満足する日の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \dots A_N
  • 1 行目には、試験期間の日数を表す整数 N が与えられる。
  • 2 行目には、各日の試験の点数を表す N 個の整数 A_1, A_2, \dots, A_N が空白区切りで与えられる。

出力

高橋君が満足する日の数を 1 行で出力してください。


入力例 1

5
60 80 50 70 90

出力例 1

4

入力例 2

5
100 50 30 20 10

出力例 2

1

入力例 3

10
50 60 40 70 30 80 20 90 10 100

出力例 3

6

入力例 4

20
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

出力例 4

20

入力例 5

1
0

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi is going through an exam period lasting N days. There is one exam each day, and Takahashi's score on the exam on day i (1 \leq i \leq N) is A_i points.

Every day, after the exam is over, Takahashi calculates the average score of all exams from day 1 through that day. If that day's score is at least the average, he feels "I did well today" and is satisfied.

Specifically, letting the average score from day 1 through day k be

M_k = \frac{A_1 + A_2 + \dots + A_k}{k}

Takahashi is satisfied on day k if A_k \geq M_k. This is equivalent to k \cdot A_k \geq A_1 + A_2 + \dots + A_k.

Note that on day 1, the average is A_1 itself, so Takahashi is always satisfied.

Given the exam scores over the N days, find the number of days on which Takahashi is satisfied.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \dots A_N
  • The first line contains an integer N representing the number of days in the exam period.
  • The second line contains N integers A_1, A_2, \dots, A_N separated by spaces, representing the exam scores for each day.

Output

Print the number of days on which Takahashi is satisfied, on a single line.


Sample Input 1

5
60 80 50 70 90

Sample Output 1

4

Sample Input 2

5
100 50 30 20 10

Sample Output 2

1

Sample Input 3

10
50 60 40 70 30 80 20 90 10 100

Sample Output 3

6

Sample Input 4

20
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

Sample Output 4

20

Sample Input 5

1
0

Sample Output 5

1