제곱수를 곁들인 수 정렬하기

양의 정수로 이루어진 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 있다. 다음 행동을 원하는 만큼 반복할 수 있다.

$1 \leq i, j \leq N$이고 $i \neq j$이면서 $A_i \times A_j$가 제곱수인 $i$, $j$를 고르고, $A_i$와 $A_j$의 값을 서로 바꾼다.

위 행동을 원하는 만큼 반복하여 수열을 비내림차순, 즉 $A_1 \le A_2 \le \cdots \le A_N$이 되도록 정렬할 수 있는지 판단하시오.

첫 번째 줄에 $N$이 주어진다. ($1 \leq N \leq 500\,000$)

두 번째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 10^{18}$)

위 행동을 원하는 만큼 반복하여 수열을 비내림차순으로 정렬할 수 있으면 YES, 아니면 NO를 출력하시오.