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.
//package com.company;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        try {
            Solver s = new Solver();
            Reader r = new Reader();
            int n = r.nextInt();
            int mini = Integer.MIN_VALUE;
            for(int i = 0; i < n; ++i) {
                int no = r.nextInt();
                if(!s.isok(no)) {
                    mini = Math.max(no, mini);
                }
            }
            System.out.println(mini);
        }
        catch (Exception e) {
            e.printStackTrace();
        }
    }


}

class Solver {

    public boolean isok(int a) {
        double d = Math.sqrt(a);
        int di = (int) d;
        if(d != di) return false;
        return true;
    }

    public void solve() {

    }
}

class Reader {
    final private int bufferSize = 1 << 16;
    private DataInputStream din;
    private byte buffer[];
    private int bufferPointer, bytesRead;
    private StringTokenizer st;

    public Reader() {
        din = new DataInputStream(System.in);
        buffer = new byte[bufferSize];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String fileName) throws IOException {
        din = new DataInputStream(new FileInputStream(fileName));
        buffer = new byte[bufferSize];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException {
        byte[] buf = new byte[64];
        int cnt = 0, c;
        while((c = read()) != -1) {
            if(c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public String next() throws IOException {
        while(st == null || !st.hasMoreElements()) {
            st = new StringTokenizer(readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while(c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if(neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while((c = read()) >= '0' && c <= '9');
        if(neg)
            return -ret;
        return  ret;
    }

    public long nextLong() throws IOException {
        long ret = 0;
        byte c = read();
        while(c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if(neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while((c = read()) >= '0' && c <= '9');
        if(neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException {
        double ret = 0, div = 1;
        byte c = read();
        while(c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if(neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while((c = read()) >= '0' && c <= '9');
        if(c == '.') {
            while((c = read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }
        if(neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException {
        bytesRead = din.read(buffer, bufferPointer = 0, bufferSize);
        if(bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException {
        if(bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException {
        if(din == null)
            return;
        din.close();
    }
}
