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.util.*;
import java.io.*;

public class Solution2 {


    private void solve() throws IOException {
        int[] squares = new int[1001];
        for (int i = 0; i < 1001; i++) {
            squares[i] = i * i;
        }
        int n = in.nextInt();
        int max = -1000001;
        for (int i = 0; i < n; i++) {
            int p = in.nextInt();
            boolean sq = false;
            for (int j = 0; j < 1001; j++) {
                if (p == squares[j]) {
                    sq = true;
                    break;
                }
            }
            if (!sq) {
                if (p > max) max = p;
            }
        }
        System.out.println(max);
    }

    private static String filename = "";
    private PrintWriter out;
    private MyScanner in;

    private void run() throws IOException {
        in = new MyScanner();
        out = new PrintWriter(System.out);
        solve();
        in.close();
        out.close();
    }

    private class MyScanner {
        private BufferedReader br;
        private StringTokenizer st;

        MyScanner() throws IOException {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public MyScanner(String fileTitle) throws IOException {
            this.br = new BufferedReader(new FileReader(fileTitle));
        }

        public String nextLine() throws IOException {
            String s = br.readLine();
            return s == null ? "-1" : s;
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return "-1";
                }
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public Integer nextInt() throws IOException {
            return Integer.parseInt(this.next());
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(this.next());
        }

        public Double nextDouble() throws IOException {
            return Double.parseDouble(this.next());
        }

        void close() throws IOException {
            this.br.close();
        }
    }

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Solution2().run();
    }
}


