Cho dãy số gồm \(𝑛\) số nguyên không âm \(𝑎_1,𝑎_2,…,𝑎_𝑛\). 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 \(𝑛 (1≤𝑛≤10^6)\).

Dòng thứ hai chứa \(𝑛\) số nguyên \(𝑎_1,𝑎_2,…,𝑎_𝑛 (0≤𝑎_𝑖≤10^12)\), 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.

Scoring

Subtask \(1\): \(50\%\) số test đầu tiên có \(𝑛≤10,0≤𝑎_𝑖≤10^4\).
Subtask \(2\): \(30\%\) số test tiếp theo có \(10^3<𝑛≤10^6,0≤𝑎_𝑖≤10^6\).
Subtask \(3\): \(20\%\) số test cuối cùng có \(0≤𝑎_𝑖≤10^12\).

8
0 3 4 2 1 4 16 25

9