Given an array a_1, a_2, ..., a_{n} 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 = y^2.


-----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 a_1, a_2, ..., a_{n} ( - 10^6 ≤ a_{i} ≤ 10^6) — 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.

Difficulty: competition

Starter code:

Solutions:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a.reverse()
for i in a:
    if i < 0:
        print(i)
        return
    if int(i ** 0.5) ** 2 != i:
        print(i)
        return

n = int(input())
a = [int(i) for i in input().split()]
x = -10**7
for i in a:
	if i < 0 or round(i ** 0.5) ** 2 != i:
		x = max(x, i)
print(x)

n = int(input())
a = list(map(int, input().split()))
a.sort()
import math
for i in a:
	if i < 0:
		r = i
	elif int(math.sqrt(i))**2 != i:
		r = i
print(r)

from math import sqrt

n = int(input())
A = list(map(int, input().split()))
print(max(a for a in A if a < 0 or int(sqrt(a))**2 != a))


n=int(input())
ar=sorted(list(map(int,input().split())))
mx=-float('inf')
for x in ar:
    if x<0:
        mx=x
        continue
    el=round(x**0.5)
    if el**2!=x:
        mx=x
print(mx)

n=int(input())
ip=list(map(int,input().split()))
high=-10000000
for i in ip:
    if i>high:
        if i<0:
            high=i
        else:
            if (i**0.5)%1==0:
                pass
            else:
                high=i
print(high)


def isqrt(n):
    if n < 0:
        return None
    elif 0 <= n <= 1:
        return n
    x = n // 2
    seen = set([x])
    while x * x != n:
        x = (x + (n // x)) // 2
        if x in seen:
            return None
        seen.add(x)
    return x

def is_square(n):
    return isqrt(n) is not None

n = int(input())
a = [int(v) for v in input().split()]

print(max(v for v in a if not is_square(v)))


import itertools

n = int(input())
vals = list(map(int, input().split()))

def is_square(x):
  if x < 0:
    return False
  for i in itertools.count():
    if i**2 == x:
      return True
    if i**2 > x:
      return False

res = -10**6 - 1
for x in vals:
  if x > res:
    if not is_square(x):
      res = x

print(res)


from math import *
def is_it_square(x):
  if x<0:
    return False
  return floor(sqrt(x))**2 == x

n=int(input())
l=[int(x) for x in input().split()]
l.sort()
l.reverse()
for x in l:
  if is_it_square(x):
    continue
  print(x)
  return

# list(map(int, input().split()))
from math import sqrt
n = int(input())
ans = -1e9
z = list(map(int, input().split()))
for t in z:
    if (t < 0):
        ans = max(t, ans)
    else:
        p = int(sqrt(t))
        while (p + 1) * (p + 1) <= t:
            p += 1
        while p * p > t:
            p -= 1
        if p * p != t:
            ans = max(ans, t)
print(ans)



import math

_ = input()

m = None
aa = list(map(int, input().split()))

print(max([a for a in aa if a < 0 or (int(math.sqrt(a)) * int(math.sqrt(a)) != a)]))


def square(n):
    if n<0:
        return False
    lo=0
    hi=n
    while lo+1<hi:
        mid=(lo+hi)//2
        if mid*mid>n:
            hi=mid
        if mid*mid<n:
            lo=mid
        if mid*mid==n:
            return True
    if lo*lo==n or hi*hi==n:
        return True
    return False

n=int(input())
line=input().split()

best=-10**7
for i in range(n):
    a=int(line[i])
    if not square(a):
        best=max(best,a)
print (best)


#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    al = set([int(i) for i in input().split()])
    for i in range(1001):
        al = al - set([i * i])
    print(max(al))

def __starting_point():
    solve()

__starting_point()

n = int(input())
x = list(map(int,input().split()))
x.sort()
for i in range(n - 1, -1, -1):
	if x[i] < 0:
		print(x[i])
		break
	if x[i] ** 0.5 % 1 != 0:
		print(x[i])
		break


n = int(input())
best = -1000000000
for i in map(int,input().split()):
    if i<0:
        best = max(best,i)
        continue
    if (i**0.5!=int(i**0.5)):
        best = max(best,i)


print(best)


input()
sqrs = set()
x = 0
while x ** 2 <= 10 ** 6:
    sqrs.add(x ** 2)
    x += 1

print(max([x for x in map(int, input().split()) if x not in sqrs]))


n=int(input())
a=list(map(int,input().strip().split(' ')))
ans=-10000000
for i in a:
    if i<0:
        if i>ans:
            ans=i
    else:
        if int(i**0.5)**2!=i and i>ans:
            ans=i
print(ans)

n=int(input())
l=list(map(int,input().split()))
ls=[]
for i in range(n):
    x=0
    if l[i]>=0:
        x=int(l[i]**0.5)
    if l[i]!=x*x or l[i]<0:
        ls.append(l[i])
ls.sort()
print(ls[-1])

from math import sqrt
input();a=list(map(int,input().split()));max=-1000000
for i in a:
    if i>=0:
        if not sqrt(i).is_integer():
            if i>max:
                max=i
    elif(i>max):
        max=i
print(max)


n = int(input())
a = list(map(int, input().split()))

def isSquare(a):
  if a < 0:
    return False
  l, r = 0, 1000001
  while r - l > 1:
    mid = r + l >> 1
    if mid * mid > a:
      r = mid
    else :
      l = mid
  return l * l == a
print(max(x for x in a if not isSquare(x)))



n = int(input())
a = [int(i) for i in input().split()]
mn = -100000000000000
for i in a:
    if i < 0:
        mn = max(mn, i)
        continue
    v = int(i ** 0.5)
    if v * v != i and (v + 1) * (v + 1) != i and (v - 1) * (v - 1) != i:
        mn = max(mn, i)
print(mn)


n = int(input())

ans = -10**18

for a in map(int, input().split()):
    if a < 0:
        ans = max(ans, a)
        continue
    t = int(a**0.5)
    if not ((t - 1)**2 == a or t**2 == a or (t + 1)**2 == a):
        ans = max(ans, a)

print(ans)


import math
    

# int(input())
# [int(i) for i in input().split()]

n = int(input())
a = [int(i) for i in input().split()]

ans = -10000000

for x in a:
    if x < 0:
        if  x > ans: ans = x
        continue
    if int(math.sqrt(x))*int(math.sqrt(x)) != x and x > ans:
        ans = x

print(ans)


from sys import stdin, stdout

n = int(stdin.readline())
values = sorted(list(map(int, stdin.readline().split())))

ans = min(values)

for i in range(n):
    
    if values[i] >= 0:
        x = values[i] ** 0.5
        
        if int(x) != x:
            ans = max(ans, values[i])        
        
    else:
        ans = values[i]

stdout.write(str(ans))

d = set([])
for i in range(1002):
    s = i*i
    d.add(s)

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
for i in a:
    if i not in d:
        print(i)
        break