#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