Trong tiết sinh hoạt lớp, giáo viên chủ nhiệm tổ chức hoạt động phát quà cho các bạn học sinh trong lớp chuyên. Giáo viên phát quà cho học sinh theo quy tắc sau:
- Mỗi học sinh sẽ đem theo một số lượng viên kẹo tùy ý.
- Học sinh xếp thành hàng ngang theo chiều tăng dần (từ trái qua phải) của số kẹo mà mình có.
- Học sinh nào đứng ở vị trí có số thứ tự trùng với số viên kẹo mình đem theo thì sẽ được ưu tiên phát quà trước, tiếp theo giáo viên sẽ phát quà cho các bạn còn lại.
Biết rằng có \(N\) học sinh, học sinh thứ \(i\) đem theo \(a_i\) viên kẹo.
Yêu cầu. Hãy đếm xem có bao nhiêu học sinh được ưu tiên phát quà trước.
\InputFile
- Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^6)\).
- Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((1 \le a_i \le 10^9)\).
\OutputFile
- In ra một số nguyên là số lượng học sinh được ưu tiên phát quà trước.
\Examples
\beginexample
\exmp
5
3 3 4 3 6
2
\exmp
5
5 3 4 7 6
0
\endexample
\Note
Ở ví dụ thứ nhất, sau khi sắp xếp dãy tăng dần ta được \(3, 3, 3, 4, 6\). Hai học sinh ở vị trí \(3\) (có \(3\) kẹo) và vị trí \(4\) (có \(4\) kẹo) được ưu tiên phát quà.
\Scoring
- (50%) \(N \le 10^3\);
- (50%) Không có ràng buộc thêm.
\endproblem
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.