Số chính phương là số tự nhiên có thể biểu diễn 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.

Cho dãy gồm n số nguyên a1, a2, ..., an.

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

Input

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10^6)
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (0 ≤ ai ≤ 10^12)

Output

In ra số chính phương nhỏ nhất không xuất hiện trong dãy.

Sample Input

8
0 3 4 2 1 4 16 25

Sample Output

9

Giới hạn

• 50% số test: n ≤ 10^3, 0 ≤ ai ≤ 10^4
• 30% số test: 10^3 < n ≤ 10^6, 0 ≤ ai ≤ 10^6
• 20% số test: 0 ≤ ai ≤ 10^12