[HSG-QH_TPHT_HT_24] Số chính phương

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên (chẳng hạn ~0, 1, 4, 9~ là các số chính phương; ~3, 7, 10~ không phải là số chính phương).

Cho số nguyên dương ~N~ và dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~.

Yêu cầu

Tìm số chính phương nhỏ nhất không xuất hiện trong dãy đã cho.

Dữ liệu đầu vào

Gồm hai dòng:

  • Dòng thứ nhất 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, ..., a_N~ ~(0 \le a_{i} \le 10^{12},\ i = 1, 2, ..., N)~ các số ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên là kết quả tìm được.

Ràng buộc dữ liệu

  • Có 40% test ứng với 40% số điểm có ~N \le 10^3,\ 0 \le a_{i} \le 10^3~;
  • Có 30% test ứng với 30% số điểm có ~10^3 < N \le 10^6,\ 0 \le a_{i} \le 10^6~;
  • Có 30% test ứng với 30% số điểm có ~10^3 < N \le 10^6,\ 10^6 \le a_{i} \le 10^{12}~;

Ví dụ

Ví dụ 1
INPUT
5
1 9 2 0 16
OUTPUT
4

Bình luận

Hãy đọc nội quy trước khi bình luận.