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 khác. Ví dụ: 0, 1, 4, 9, 16, 25, … là các số chính phương, còn các số 2, 3, 5, … không là số chính phương.

Cho dãy gồm \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\). Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Dữ liệu vào: nhập từ bàn phím:

- Dòng đầu tiên chứa số nguyên \(n\) (\(1\ \leq n \leq 10^{6})\);

- Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ \) \(({0 \leq a}_{i} \leq 10^{12},\ i = 1,\ 2,\ \ldots,\ n)\), các số cách nhau một dấu cách.

Dữ liệu ra: in ra màn hình kết quả tìm được.

Ví dụ:

Input	Output
8 0 3 4 2 1 4 16 25	9

Ràng buộc:

+ Có 50% số test tương ứng với 50% số điểm của câu có \(1 \leq n \leq 10^{3},\ 0 \leq a_{i} \leq 10^{4}\);

+ Có 30% số test tương ứng với 30% số điểm của câu có \(10^{3} < n \leq 10^{6},0 \leq a_{i} \leq 10^{6}\);

+ Có 20% số test tương ứng với 20% số điểm của câu có \(0 \leq a_{i} \leq 10^{12}\).