~Molang~ được giao nhiệm vụ làm giám thị cho một buổi thi. Phòng thi mà ~Molang~ được giao bao gồm một hàng ghế gồm ~N~ thí sinh đánh số từ ~1~ đến ~N~. Các thí sinh ngồi thẳng đều từ trên xuống, vì vậy nếu như không thuộc bài thì chỉ có thể chép bài từ những người phía trước (trừ thí sinh ngồi bàn đầu).
Điều đặc biệt là mỗi thí sinh có một nhãn quan khác nhau gọi là ~a_i~. Thí sinh thứ ~i~ có thể chép bài thí sinh thứ ~j~ khi và chỉ khi ~i - a_i \leq j < i~.
~Molang~ được cung cấp nhãn quan của mỗi thí sinh. ~Molang~ tò mò muốn biết có bao nhiêu thí sinh may mắn không bị chép bài trong buổi thi đó. Là một lập trình viên bạn hãy giúp ~Molang~ nhé.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên ~N~ ( ~1 \leq N \leq 5 \times 10^6 ~) — số thí sinh dự thi.
Dòng thứ hai chứa ~N~ số nguyên cách nhau bởi dấu cách ~a_1 , a_2, \dots, a_N ~ ( ~0 \leq a_i \leq 10^7 ~), trong đó ~a_i~ là nhãn quan của thí sinh thứ ~i~ .
Kết quả ra
- In ra một số nguyên — tổng số thí sinh không bị chép bài sau khi kết thúc buổi thi.
Ràng buộc
- Subtask ~1~ (~40 \%~): ~1 \leq N \leq 1000~.
- Subtask ~2~ (~30 \%~): ~1 \leq N \leq 5 \times 10^5~.
- Subtaks ~3~ (~30 \%~): Không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu vào
4
0 1 0 10
Kết quả ra
1
Giải thích
- Thí sinh ~1~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~2~: Chép được bài của thí sinh ~1~.
- Thí sinh ~3~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~4~: Chép được bài của các thí sinh: ~1~, ~2~, ~3~.
~\to~ Chỉ có thí sinh ~4~ không bị chép bài.
Ví dụ 2
Dữ liệu vào
2
0 0
Kết quả ra
2
Giải thích
- Thí sinh ~1~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~2~: Không chép được bài của các thí sinh phía trước.
~\to~ Thí sinh ~1~ và ~2~ đều không bị chép bài.
Ví dụ 3
Dữ liệu vào
8
1 1 0 0 0 2 0 3
Kết quả ra
3
Giải thích
- Thí sinh ~1~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~2~: Chép được bài của các thí sinh: ~1~.
- Thí sinh ~3~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~4~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~5~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~6~: Chép được bài của các thí sinh: ~4~, ~5~.
- Thí sinh ~7~: Không chép được bài của các thí sinh phía trước.
- Thí sinh ~8~: Chép được bài của các thí sinh: ~5~, ~6~, ~7~.
- ~\to~ Thí sinh ~2~, ~3~ và ~8~ đều không bị chép bài.
Bình luận