제곱수 수열

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

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

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

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

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