Perfect Square Sum Sequence

You are given an integer \(N\) and a sequence of \(N\) integers \(A = [a_1, a_2, \dots, a_N]\). Your task is to determine whether it is possible to permute the sequence into an order such that the sum of every two consecutive numbers is a perfect square. A number \(s\) is a perfect square if there exists an integer \(k\) such that \(s = k^2\). For example, since \(1 + 3 = 4\) and \(4 = 2^2\), the pair (1, 3) forms a valid consecutive pair.

If there exists at least one permutation of \(A\) meeting the condition, output YES; otherwise, output NO.

Examples:

• For \(N=3\) and \(A = [1, 17, 8]\), one valid permutation is \([1, 8, 17]\) since \(1+8=9=3^2\) and \(8+17=25=5^2\); hence the output is YES.
• For \(N=4\) and \(A = [1, 14, 2, 3]\), no permutation satisfies the condition, so the output is NO.

inputFormat

The input is given via standard input and consists of two lines:

1. The first line contains a single integer \(N\), representing the number of elements in the sequence.
2. The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\), representing the sequence.

outputFormat

Output a single line with YES if there exists a permutation of the sequence such that the sum of every two consecutive numbers is a perfect square. Otherwise, output NO.

3
1 17 8

YES