Cho dãy ~n~ số nguyên không âm. Hãy tìm số chính phương nhỏ nhất không xuất hiện trong dãy.

Input

Dòng đầu chứa ~n~ ~(1 \le n \le 10^6)~.

Dòng hai chứa ~n~ số ~a_i~ ~(0 \le a_i \le 10^{12})~.

Output

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

Bộ test gồm 50 testcase, có test biên, test subtask nhỏ và test sát giới hạn.

Subtask

• 50% s? ?i?m: ~n \le 10^1~, ~0 \le a_i \le 10^4~.
• 30% s? ?i?m: ~10^3 < n \le 10^6~, ~0 \le a_i \le 10^6~.
• 20% s? ?i?m: ~1 \le n \le 10^6~, ~0 \le a_i \le 10^{12}~.