小月的排序
题号：NC307921
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定长度为 n 的正整数数组 a_1,a_2,\dots,a_n，你可以任意次执行下面的操作：
\hspace{23pt}\bullet\,选择两个不同下标 i\neq j，如果 a_i\times a_j 是完全平方数^\texttt{[1]}，则交换 a_i 和 a_j。
\hspace{15pt}求解：能否通过若干次这样的操作把数组变为单调不降^\texttt{[2]}的？

【名词解释】
\hspace{15pt}完全平方数^\texttt{[1]}：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。前十个完全平方数是 0,1,4,9,16,25,36,49,64,81。
\hspace{15pt}单调不降^\texttt{[2]}：对于数组 a 中从左向右数的第 i 个元素 a_i ，如果 a_{i+1} 存在，那么 a_i \leqq a_{i+1}。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1\leq n\leq 10^5\right)，表示数组长度。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(1\leq a_i\leq 10^6\right)，表示数组中的元素。

输出描述:

\hspace{15pt}如果可以通过若干次这样的操作把数组变为单调不降的，输出 \texttt{YES}，否则输出 \texttt{NO}。
示例1

输入

复制 
3
9 1 4

输出

复制 
YES

说明

\hspace{15pt}在这个样例中，其中一种可行的方案是：
\hspace{23pt}\bullet\,选择 i=1 和 j=2，因为 9\times 1 = 9=3^2，是完全平方数，可以交换，数组变为 \{{\color{orange}{1}},{\color{orange}{9}},4\}；
\hspace{23pt}\bullet\,选择 i=2 和 j=3，因为 9\times 4 = 36 = 6^2，是完全平方数，可以交换，数组变为 \{1,{\color{orange}{4}},{\color{orange}{9}}\}。
\hspace{15pt}综上，数组可以变成单调不降的。
示例2

输入

复制 
5
1 2 3 1 2

输出

复制 
NO
示例3

输入

复制 
4
1 2 3 4

输出

复制 
YES