#include <bits/stdc++.h>
using namespace std;
bool is_vowel(char x) {
  if (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u') return true;
  if (x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U') return true;
  if (x == 'y' or x == 'Y') return true;
  return false;
}
bool is_palindrome(string s) {
  int len = s.length();
  int n = len - 1;
  for (int i = 0; i < len; ++i, --n) {
    if (s[i] != s[n]) return false;
  }
  return true;
}
string to_str(long long x) {
  string ans = "";
  while (x != 0) {
    int d = x % 10;
    char c = (int)d + 48;
    ans.push_back(c);
    x = x / 10;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
bool is_prime(long long x) {
  if (x == 1 or x == 0) return false;
  if (x == 2) return true;
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) return false;
  }
  return true;
}
int car_todig(char x) { return x - 48; }
char dig_tocar(int x) { return x + 48; }
bool is_upper(char x) {
  if (x >= 'A' and x <= 'Z')
    return true;
  else
    return false;
}
bool is_lower(char x) {
  if (x >= 'a' and x <= 'z')
    return true;
  else
    return false;
}
bool is_digit(char x) {
  if (x >= '0' and x <= '9')
    return true;
  else
    return false;
}
long long get_ceil(long long d, long long val) {
  if (d % val == 0)
    return d / val;
  else
    return (d / val) + 1;
}
void solve() {
  int n;
  cin >> n;
  vector<long long> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  sort(v.rbegin(), v.rend());
  for (int i = 0; i < n; ++i) {
    long long s = (long long)sqrt(v[i]);
    if (s * s != v[i]) {
      cout << v[i] << endl;
      return;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    solve();
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool is_vowel(char x) {
  if (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u') return true;
  if (x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U') return true;
  if (x == 'y' or x == 'Y') return true;
  return false;
}
bool is_palindrome(string s) {
  int len = s.length();
  int n = len - 1;
  for (int i = 0; i < len; ++i, --n) {
    if (s[i] != s[n]) return false;
  }
  return true;
}
string to_str(long long x) {
  string ans = "";
  while (x != 0) {
    int d = x % 10;
    char c = (int)d + 48;
    ans.push_back(c);
    x = x / 10;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
bool is_prime(long long x) {
  if (x == 1 or x == 0) return false;
  if (x == 2) return true;
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) return false;
  }
  return true;
}
int car_todig(char x) { return x - 48; }
char dig_tocar(int x) { return x + 48; }
bool is_upper(char x) {
  if (x >= 'A' and x <= 'Z')
    return true;
  else
    return false;
}
bool is_lower(char x) {
  if (x >= 'a' and x <= 'z')
    return true;
  else
    return false;
}
bool is_digit(char x) {
  if (x >= '0' and x <= '9')
    return true;
  else
    return false;
}
long long get_ceil(long long d, long long val) {
  if (d % val == 0)
    return d / val;
  else
    return (d / val) + 1;
}
void solve() {
  int n;
  cin >> n;
  vector<long long> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  sort(v.rbegin(), v.rend());
  for (int i = 0; i < n; ++i) {
    long long s = (long long)sqrt(v[i]);
    if (s * s != v[i]) {
      cout << v[i] << endl;
      return;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    solve();
  }
  return 0;
}

```