Given an array a1, a2, ..., an of n integers, find the largest number in the array that is not a perfect square.

A number x is said to be a perfect square if there exists an integer y such that x = y2.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an ( - 106 ≤ ai ≤ 106) — the elements of the array.

It is guaranteed that at least one element of the array is not a perfect square.

Output

Print the largest number in the array which is not a perfect square. It is guaranteed that an answer always exists.

Examples

Input

2
4 2


Output

2


Input

8
1 2 4 8 16 32 64 576


Output

32

Note

In the first sample case, 4 is a perfect square, so the largest number in the array that is not a perfect square is 2.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String str1 = in.readLine();
		int n = Integer.parseInt(str1);
		String[] arr = in.readLine().split(" ");
		int temp;
		int max = Integer.MIN_VALUE;
		while (n-- > 0) {
			temp = Integer.parseInt(arr[n]);
			if (temp > 0) {
				int t = (int) Math.sqrt(temp);
				if (t * t != temp && temp > max) {
					max = temp;
				}
			} else if(temp< 0) {
				if (temp > max)
					max = temp;
			}
		}

		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out, "UTF-8")));

		out.println(max);

		out.flush();
	}

}