Điều hướng chính

Nhắn tin NQ Coding

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

Bài tập xaynhacaotang

Xây nhà cao tầng

Dễ Sắp xếpTham lam

  • 100 Điểm
  • 1.0s Thời gian
  • 256M Bộ nhớ
  • 0% Tỉ lệ AC
  • 0 Số AC

Neko làm phụ hồ và có \(n\) căn phòng đúc sẵn để xếp chồng thành một tòa nhà (mỗi căn dùng nhiều nhất một lần, mỗi tầng đúng một căn). Căn phòng thứ \(i\) có sức chịu tải \(a_i\): nó chịu được nhiều nhất \(a_i\) căn phòng nằm phía trên nó (số phòng nằm trên trực tiếp và gián tiếp, tức là tổng số phòng ở các tầng cao hơn).

Neko có thể chọn ra một số căn phòng bất kỳ (không nhất thiết dùng hết) và sắp xếp thứ tự các tầng tùy ý. Hãy tính số tầng lớn nhất mà tòa nhà có thể đạt được.

Input

  • Dòng đầu tiên chứa số nguyên \(n\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên là số tầng lớn nhất.

Constraints

  • \(1 \le n \le 10^5\)
  • \(0 \le a_i \le n\)

Sample Input 1

6
1 5 2 2 0 3

Sample Output 1

5

Sample Input 2

4
0 0 0 0

Sample Output 2

1

Explanation

  • Ví dụ 1: xếp từ trên xuống dưới các phòng có sức chịu tải \(0, 1, 2, 3, 5\) (bỏ một trong hai phòng có \(a = 2\)): phòng ở tầng thứ \(j\) (đếm từ trên, bắt đầu từ \(0\)) cần \(a \ge j\) nên đều thỏa mãn. Dùng cả \(6\) phòng thì không được: phòng có sức chịu tải \(0\) phải ở trên cùng, phòng có \(1\) ở tầng kế tiếp, và cứ thế hai phòng có \(a = 2\) không thể cùng chịu được vị trí thứ \(3\) trở xuống.
  • Ví dụ 2: mọi phòng đều không chịu được phòng nào ở trên nên chỉ dùng được \(1\) phòng.

Bình luận

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