#197 제곱수 수열

문제

$N$ 개의 양의 정수가 주어진다. 이중 일부를 재배열해서 모든 연속된 두 수의 곱이 제곱수인 가장 긴 수열을 만들어라.

첫째 줄에 수의 개수 $N$ 이 주어진다. $(1 \le N \le 10^{6})$

둘째 줄에 $N$ 개의 양의 정수 $A_{1}$ , , , 이 공백으로 구분되어 주어진다.

첫째 줄에 만든 수열의 길이를 출력하라.

둘째 줄에 만든 수열을 공백으로 구분해 출력하라. 이때 그러한 수열이 여럿일 수 있으므로 그중 사전순으로 제일 앞에 오는 수열을 출력하라.

#	得点	制約
1	100	-

例 1

入力例

8
1 2 4 8 16 32 64 128

出力例

4
1 4 16 64

例 2

入力例

8
4 2 4 8 16 32 64 128

出力例

4
2 8 32 128

例 3

入力例

8
4 8 4 8 16 32 64 128

出力例

4
4 4 16 64

例 4

入力例

5
2 3 5 7 11

出力例

1
2