/
実行時間制限: 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