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.
from math import sqrt
n=input()
t=input().split(' ')
l=[]
def isSquare(a):
  if a<0:
    return False
  if a==0:
      return True
  for k in range(1,a+1):
  
    if k*k==a:
      return True
    if k*k> a:
      return False
  return False
for k in t:
  if k:
    l.append(int(k))
l=reversed(sorted(l))
for k in l:
  if not isSquare(k):
    print(k)
    break