An đang ngồi học lập trình nhưng có một bài làm An bối rối, bạn hãy giúp An giải quyết bài toán đó nhé.

Bài toán như sau: Cho dãy số gồm ~n~ số nguyên không âm ~a_1, a_2,..., a_n~. Hãy tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Biết rằ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

Input

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, ..., a_n~ ~(0 \le a \le 10^{12}, i = 1, 2, ..., n)~, các số cách nhau một dấu cách.

Output

Một số nguyên duy nhất là kết quả của bài toán

Subtask

• Subtask 1: ~50\%~ số test đầu tiên ~n \le 10 ^ 1 0 \le a_{i} \le 10 ^ 4~
• Subtask 2: ~30\%~ số test tiếp theo ~10 ^ 3 < n \le 10 ^ 6 0 \le a_{i} \le 10 ^ 6~
• Subtask 3: ~20\%~ số test cuối cùng ~0 \le a_{i} \le 10 ^ {12}~

Sample Input

8 
0 3 4 2 1 4 16 25

Sample Output

9