#197 제곱수 수열

문제

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

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

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

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

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

#	Score	Constraints
1	100	-

Sample 1

Input

8
1 2 4 8 16 32 64 128

Output

4
1 4 16 64

Sample 2

Input

8
4 2 4 8 16 32 64 128

Output

4
2 8 32 128

Sample 3

Input

8
4 8 4 8 16 32 64 128

Output

4
4 4 16 64

Sample 4

Input

5
2 3 5 7 11

Output

1
2