A - Distributing Presents Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、 N 人の友人にプレゼントを届けるため、友人 1 、友人 2 、…、友人 N の順に家を訪問します。

高橋君は最初、プレゼントを N 個持っています。しかし、各友人の家に向かう道中には障害物があり、つまずいてプレゼントを落としてしまうことがあります。

友人 i の家に向かう途中で、高橋君はちょうど F_i 回つまずきます。つまずくたびに、その時点で持っているプレゼントの数が 1 個以上であれば、プレゼントを 1 個落として失ってしまい、持っているプレゼントの数が 1 減ります。持っているプレゼントが 0 個の状態でつまずいた場合は、何も起こりません。

友人 i の家に到着したとき、高橋君が持っているプレゼントが 1 個以上であれば、プレゼントを 1 個渡します。このとき、持っているプレゼントの数が 1 減ります。プレゼントを 1 個も持っていなければ、何も渡せません。

すべての友人を訪問し終えた後、プレゼントを受け取ることができた友人の人数を求めてください。

制約

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

入力

N
F_1
F_2
\vdots
F_N
  • 1 行目には、友人の人数を表す整数 N が与えられる。
  • 1 + i 行目 (1 \leq i \leq N) には、友人 i の家に向かう途中でつまずく回数 F_i が与えられる。

出力

プレゼントを受け取ることができた友人の人数を 1 行で出力してください。

入力例 1

5
0
1
0
2
0

出力例 1

3

入力例 2

4
0
0
0
0

出力例 2

4

入力例 3

10
0
2
0
1
0
3
0
0
1
0

出力例 3

5

入力例 4

25
0
0
1
0
2
0
0
1
3
0
0
0
2
1
0
4
0
0
1
0
2
0
0
5
0

出力例 4

15

入力例 5

1
1000000000

出力例 5

0

Score : 233 pts

Problem Statement

Takahashi will visit his friends' houses in the order of Friend 1, Friend 2, ..., Friend N to deliver presents to his N friends.

Takahashi initially holds N presents. However, there are obstacles on the way to each friend's house, and he may stumble and drop presents.

On the way to Friend i's house, Takahashi stumbles exactly F_i times. Each time he stumbles, if he holds at least 1 present at that moment, he drops and loses 1 present, reducing the number of presents he holds by 1. If he stumbles while holding 0 presents, nothing happens.

Upon arriving at Friend i's house, if Takahashi holds at least 1 present, he gives 1 present to the friend. In this case, the number of presents he holds decreases by 1. If he holds no presents, he cannot give anything.

Find the number of friends who received a present after Takahashi has visited all his friends.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq F_i \leq 10^9
  • All input values are integers.

Input

N
F_1
F_2
\vdots
F_N
  • The 1-st line contains an integer N, representing the number of friends.
  • The (1 + i)-th line (1 \leq i \leq N) contains an integer F_i, representing the number of times Takahashi stumbles on the way to Friend i's house.

Output

Print the number of friends who received a present in a single line.

Sample Input 1

5
0
1
0
2
0

Sample Output 1

3

Sample Input 2

4
0
0
0
0

Sample Output 2

4

Sample Input 3

10
0
2
0
1
0
3
0
0
1
0

Sample Output 3

5

Sample Input 4

25
0
0
1
0
2
0
0
1
3
0
0
0
2
1
0
4
0
0
1
0
2
0
0
5
0

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

0