914_A. Perfect Squares_10344
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.
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int max = -10000001;
  int a;
  for (int i = 0; i < n; i++) {
    cin >> a;
    if (a < 0) {
      if (a > max) {
        max = a;
      }
    } else {
      int root = sqrt(a);
      if (root * root != a) {
        if (a > max) {
          max = a;
        }
      }
    }
  }
  cout << max << "\n";
  return 0;
}

2
4 2
 8
1 2 4 8 16 32 64 576
 2
370881 659345
 5
804610 765625 2916 381050 93025
 1
-1000000
 2
-1 0
 2
99999 3
 53
280988 756430 -515570 -248578 170649 -21608 642677 216770 827291 589500 940901 216097 -118956 -919104 -319264 -761585 289479 499613 588276 883036 480518 -323196 -274570 -406556 -381484 -956025 702135 -445274 -783543 136593 153664 897473 352651 737974 -21123 -284944 501734 898033 604429 624138 40804 248782 -786059 -304592 -209210 -312904 419820 -328648 -47331 -919227 -280955 104827 877304
 2
15 131073
 1
-917455
 71
908209 289 44521 240100 680625 274576 212521 91809 506944 499849 3844 15376 592900 58081 240100 984064 732736 257049 600625 180625 130321 580644 261121 75625 46225 853776 485809 700569 817216 268324 293764 528529 25921 399424 175561 99856 295936 20736 611524 13924 470596 574564 5329 15376 676 431649 145161 697225 41616 550564 514089 9409 227529 1681 839056 3721 552049 465124 38809 197136 659344 214369 998001 44944 3844 186624 362404 -766506 739600 10816 299209
 30
192721 -950059 -734656 625 247009 -423468 318096 622521 678976 777924 1444 748303 27556 62001 795664 89401 221841 -483208 467856 477109 196 -461813 831744 772641 574564 -519370 861184 67600 -717966 -259259
 3
-1 -4 -9
 1
-1
 1
-439
 2
0 -5
 3
1 1 -1
 2
-5 0
 15
256 -227055 427717 827239 462070 66049 987533 -175306 -552810 -867915 -408251 -693957 -972981 -245827 896904
 16
-882343 -791322 0 -986738 -415891 -823354 -840236 -552554 -760908 -331993 -549078 -863759 -913261 -937429 -257875 -602322
 2
4 5
 2
-1000000 1000000
 3
-1 -2 -3
 2
-524272 -1000000
 1
2
 2
3 4
 35
-871271 -169147 -590893 -400197 -476793 0 -15745 -890852 -124052 -631140 -238569 -597194 -147909 -928925 -587628 -569656 -581425 -963116 -665954 -506797 -196044 -309770 -701921 -926257 -152426 -991371 -624235 -557143 -689886 -59804 -549134 -107407 -182016 -24153 -607462
 2
131073 1
 3
-1 -2 0
 3
-1 1 0
 5
984065 842724 127449 525625 573049
 2
226505 477482
 2
999999 1000000
 5
918375 169764 598796 76602 538757
 35
628849 962361 436921 944784 444889 29241 -514806 171396 685584 -823202 -929730 6982 198025 783225 552049 -957165 782287 -659167 -414846 695556 -336330 41616 963781 71289 119639 952576 -346713 178929 232324 121802 393266 841 649636 179555 998001
 2
370881 561101
 5
804610 765625 2916 664938 93025
 2
-1 1
 2
108034 3
 53
280988 756430 -515570 -248578 170649 -21608 642677 216770 827291 589500 940901 216097 -118956 -919104 -319264 -761585 289479 499613 588276 883036 480518 -323196 -274570 -406556 -381484 -956025 702135 -445274 -783543 136593 153664 897473 352651 737974 -21123 -284944 501734 898033 604429 624138 40804 248782 -786059 -304592 -209210 -312904 419820 -328648 -47331 -919227 -280955 91536 877304
 2
22 131073
 1
-505594
 30
192721 -950059 -734656 625 247009 -423468 318096 622521 678976 777924 1444 748303 27556 62001 795664 89401 221841 -483208 467856 477109 196 -461813 831744 772641 574564 -519370 861184 67600 -1015561 -259259
 1
-2
 1
-856
 2
-5 1
 15
256 -227055 427717 827239 462070 66049 987533 -175306 -602310 -867915 -408251 -693957 -972981 -245827 896904
 16
-882343 -791322 0 -986738 -415891 -823354 -840236 -552554 -1038535 -331993 -549078 -863759 -913261 -937429 -257875 -602322
 2
-1000000 0000000
 2
-524272 -1142460
 2
3 0
 35
-871271 -169147 -590893 -400197 -283959 0 -15745 -890852 -124052 -631140 -238569 -597194 -147909 -928925 -587628 -569656 -581425 -963116 -665954 -506797 -196044 -309770 -701921 -926257 -152426 -991371 -624235 -557143 -689886 -59804 -549134 -107407 -182016 -24153 -607462
 2
114406 1
 5
984065 842724 127449 449303 573049
 2
226505 59159
 5
918375 169764 824706 76602 538757
 35
628849 962361 436921 944784 444889 29241 -514806 171396 685584 -1137886 -929730 6982 198025 783225 552049 -957165 782287 -659167 -414846 695556 -336330 41616 963781 71289 119639 952576 -346713 178929 232324 121802 393266 841 649636 179555 998001
 2
6 2
 8
1 2 4 8 16 32 64 1122
 2
370881 416356
 5
575541 765625 2916 664938 93025
 2
156081 3
 2
22 34093
 1
-640899
 30
192721 -950059 -734656 625 247009 -423468 318096 622521 953585 777924 1444 748303 27556 62001 795664 89401 221841 -483208 467856 477109 196 -461813 831744 772641 574564 -519370 861184 67600 -1015561 -259259
 1
-4
 1
-756
 3
2 0 -1
 2
-37401 -1142460
 35
-871271 -169147 -590893 -400197 -283959 0 -15745 -890852 -124052 -631140 -238569 -597194 -147909 -928925 -587628 -569656 -581425 -963116 -665954 -506797 -196044 -309770 -701921 -926257 -152426 -991371 -624235 -557143 -689886 -59804 -8559 -107407 -182016 -24153 -607462
 5
575541 987642 2916 664938 93025
 53
280988 756430 -515570 -248578 170649 -21608 642677 216770 827291 589500 940901 216097 -118956 -919104 -319264 -761585 289479 984042 588276 883036 480518 -323196 -274570 -406556 -381484 -956025 702135 -445274 -783543 136593 153664 897473 352651 737974 -21123 -284944 501734 898033 604429 624138 40804 248782 -786059 -304592 -209210 -312904 419820 -328648 -46272 -919227 -280955 91536 877304
 1
-912742
 1
-6
 1
-327
 15
256 -421397 427717 827239 462070 66049 240445 -175306 -602310 -867915 -408251 -693957 -972981 -245827 896904
 16
-882343 -791322 0 -986738 -415891 -823354 -840236 -552554 -1038535 -331993 -549078 -863759 -1823796 -22437 -257875 -602322
 2
-9230 -1142460
 2
93680 2
 2
7 1
 1
-635048
 1
-8
 1
-431
 2
79297 2
 35
628849 962361 436921 944784 444889 29241 -514806 171396 685584 -1137886 -929730 6982 198025 783225 552049 -957165 782287 -659167 -414846 695556 -438685 41616 963781 71289 120100 1026928 -346713 178929 232324 121802 393266 841 649636 179555 998001
 2
12 1
 2
78013 229706
 2
60 65295
 1
-864453
 1
-12
 1
-34
 3
-1 -4 -18
 2
0 -1
 3
1 0 -1
 3
-2 -2 -3
 3
-1 -4 0
 53
280988 756430 -515570 -248578 170649 -21608 642677 216770 827291 589500 940901 216097 -118956 -919104 -319264 -761585 289479 499613 588276 883036 480518 -323196 -274570 -406556 -381484 -956025 702135 -445274 -783543 136593 153664 897473 352651 737974 -21123 -284944 501734 898033 604429 624138 40804 248782 -786059 -304592 -209210 -312904 419820 -328648 -46272 -919227 -280955 91536 877304
 3
-1 -4 -34
 2
1 -1
 15
256 -421397 427717 827239 462070 66049 987533 -175306 -602310 -867915 -408251 -693957 -972981 -245827 896904
 16
-882343 -791322 0 -986738 -415891 -823354 -840236 -552554 -1038535 -331993 -549078 -863759 -1823796 -937429 -257875 -602322
 3
-2 -2 -5
 2
3 1
 2
114406 2
 3
-1 -4 -1
 5
984065 842724 25079 449303 573049
 2
226505 99508
 5
918375 169764 824706 3923 538757
 35
628849 962361 436921 944784 444889 29241 -514806 171396 685584 -1137886 -929730 6982 198025 783225 552049 -957165 782287 -659167 -414846 695556 -336330 41616 963781 71289 120100 952576 -346713 178929 232324 121802 393266 841 649636 179555 998001
 2
6 1
 8
1 2 3 8 16 32 64 1122
 2
205210 416356
 2
156081 5
 2
39 34093
 30
192721 -950059 -734656 625 247009 -423468 318096 622521 953585 777924 1444 748303 27556 62001 795664 89401 221841 -483208 467856 477109 196 -461813 831744 772641 574564 -519370 861184 67600 -681056 -259259
 3
-2 -4 -34
 3
0 0 -1
 3
-2 -2 -7
 2
3 2
 35
-871271 -169147 -590893 -400197 -283959 0 -15745 -890852 -124052 -391583 -238569 -597194 -147909 -928925 -587628 -569656 -581425 -963116 -665954 -506797 -196044 -309770 -701921 -926257 -152426 -991371 -624235 -557143 -689886 -59804 -8559 -107407 -182016 -24153 -607462
 3
-2 -4 -1
 5
984065 842724 809 449303 573049
 2
226505 68406
 5
918375 181385 824706 3923 538757
 35
628849 962361 436921 944784 444889 29241 -514806 171396 685584 -1137886 -929730 6982 198025 783225 552049 -957165 782287 -659167 -414846 695556 -438685 41616 963781 71289 120100 952576 -346713 178929 232324 121802 393266 841 649636 179555 998001
 8
1 2 0 8 16 32 64 1122
 2
78013 416356
 5
575541 987642 4610 664938 93025
 2
156081 8
 2
60 34093
 30
192721 -950059 -734656 625 247009 -423468 318096 622521 953585 777924 1444 748303 27556 62001 795664 89401 221841 -483208 467856 477109 196 -461813 831744 764215 574564 -519370 861184 67600 -681056 -259259
 3
-2 -7 -34
 3
0 -1 -1
 15
256 -421397 427717 827239 792868 66049 240445 -175306 -602310 -867915 -408251 -693957 -972981 -245827 896904
 16
-882343 -791322 0 -986738 -415891 -823354 -840236 -75742 -1038535 -331993 -549078 -863759 -1823796 -22437 -257875 -602322

2
 32
 659345
 804610
 -1000000
 -1
 99999
 940901
 131073
 -917455
 -766506
 748303
 -1
 -1
 -439
 -5
 -1
 -5
 987533
 -257875
 5
 -1000000
 -1
 -524272
 2
 3
 -15745
 131073
 -1
 -1
 984065
 477482
 999999
 918375
 963781
 561101
 804610
 -1
 108034
 940901
 131073
 -505594
 748303
 -2
 -856
 -5
 987533
 -257875
 -1000000
 -524272
 3
 -15745
 114406
 984065
 226505
 918375
 963781
 6
 1122
 416356
 664938
 156081
 34093
 -640899
 953585
 -4
 -756
 2
 -37401
 -8559
 987642
 984042
 -912742
 -6
 -327
 896904
 -22437
 -9230
 93680
 7
 -635048
 -8
 -431
 79297
 1026928
 12
 229706
 65295
 -864453
 -12
 -34
 -1
 -1
 -1
 -2
 -1
 940901
 -1
 -1
 987533
 -257875
 -2
 3
 114406
 -1
 984065
 226505
 918375
 963781
 6
 1122
 416356
 156081
 34093
 953585
 -2
 -1
 -2
 3
 -8559
 -1
 984065
 226505
 918375
 963781
 1122
 416356
 987642
 156081
 34093
 953585
 -2
 -1
 896904
 -22437
