Số chính phương

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, \dots, a_n$. Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Nhập từ bàn phím:

• Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^6$);
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{12}, i = 1, 2, \dots, n$), các số cách nhau một dấu cách.

In ra màn hình kết quả tìm được.

• Có 50% số test tương ứng với 50% số điểm của câu có $1 \le n \le 10^3, 0 \le a_i \le 10^4$;
• Có 30% số test tương ứng với 30% số điểm của câu có $10^3 < n \le 10^6, 0 \le a_i \le 10^6$;
• Có 20% số test tương ứng với 20% số điểm của câu có $0 \le a_i \le 10^{12}$.