Congrats on helping Mrs. Lam catch the cheaters!

However, Jason now needs your help. He wants to make a bouquet of flowers to give to a special someone, but there are a few restrictions:

1. He has \(N\) packs of flowers, each containing an integer amount of flowers.
2. The special someone prefers bouquets with an amount of flowers that is a perfect square, and will not accept anything else.
3. The bouquet of flowers should have as many flowers as possible.

Please help Jason figure out the largest amount of flowers he can make a bouquet with using the packs of flowers to satisify the special someone with a perfect bouquet

I.E. Given an array of \(N\) integers, find the largest perfect square smaller than or equal to the array's sum.

Constraints

Subtask 1 [60%]

\(1 \le N, a_{i} \le 10 ^ 4\)

Subtask 2 [40%]

\(1 \le N \le 10 ^ 6\)

\(1 \le a_{i} \le 10 ^ 9\)

Input Specification

The first line will contain the integer \(N\). The next \(N\) lines contain one integer per line, the \(a_{i}\) element of the array.

Output Specification

Output the largest perfect square smaller than or equal to the array's sum.

Sample Input 1

6
1
3
11
5
9
7

Sample Output 1

36

Explanation for Sample Output 1

The largest perfect square smaller than or equal to the sum of \(36\) is \(36\).

Sample Input 2

1
99

Sample Output 2

81