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₁, a₂, ..., 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₁, a₂, ..., 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ụ:

Dữ liệu vào

8
0 3 4 2 1 4 16 25

Dữ liệu ra

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_i ≤ 10⁴;

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

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