Điều hướng chính

Ngôn ngữ

Phím tắt

/
Chuyển đến ô tìm bài
g p
Đi đến bài tập
g c
Đi đến kỳ thi
g u
Đi đến người dùng
?
Mở trợ giúp phím tắt

Phát quà

Dễ

  • 100 Điểm
  • 50% Tỉ lệ AC
  • 8 Số AC
  • 256M Bộ nhớ giới hạn
  • 1.0s Giới hạn thời gian

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

Chưa có bình luận nào.