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, ..., 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 ≤ n ≤ 10⁶);
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n~ (0 ≤ ~a_i~ ≤ 10¹², i = 1, 2, ..., 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:

8
0 3 4 2 1 4 16 25

Output

9

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm của câu có:
  1 ≤ n ≤ 10³, 0 ≤ aᵢ ≤ 10⁴
• Có 30% số test tương ứng với 30% số điểm của câu có:
  10³ < n ≤ 10⁶, 0 ≤ aᵢ ≤ 10⁶

• Có 20% số test tương ứng với 20% số điểm của câu có:
  0 ≤ aᵢ ≤ 10¹²

  Link