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, \dots, 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, \dots\) là các số chính phương, còn các số: \(2, 3, 5, \dots\) 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, \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.

Output

• Ghi ra một dòng chứa một số nguyên không âm là số chính phương nhỏ nhất không xuất hiện trong dãy đã cho.

Example

8
0 3 4 2 1 4 16 25

9

Scoring

• Subtask \(1\) (\(50\%\) số test đầu tiên): \(n \le 10^3\), \(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}\)