Sorting Numbers with Perfect Squares

Time limit2.5sMemory limit1024 MB

Summary

Given N integers up to 10^18, decide whether swapping pairs whose product is a perfect square can sort the array into non-decreasing order.

Level: Medium6 of 10
Topics: Number theory, Sorting, Hash map
Solved: No attempts yet

Problem

You are given a sequence of $N$ positive integers $A_1, A_2, \cdots, A_N$ . You may repeat the following operation as many times as you want.

Choose two indices $i$ and $j$ with $1 \leq i, j \leq N$ and $i \neq j$ such that $A_i \times A_j$ is a perfect square, then swap the values of $A_i$ and $A_j$ .

Determine whether you can repeat the operation as many times as you want to make the sequence non-decreasing, that is, $A_1 \le A_2 \le \cdots \le A_N$ .

Input

The first line contains $N$ . ( $1 \leq N \leq 500\,000$ )

The second line contains the integers $A_1, A_2, \cdots, A_N$ separated by spaces. ( $1 \leq A_i \leq 10^{18}$ )

Output

If you can sort the sequence into non-decreasing order by repeating the operation as many times as you want, print YES. Otherwise, print NO.

Examples2

Example 1
Input
```
4
1 27 3 12
```
Expected output
```
YES
```
Example 2
Input
```
2
2 1
```
Expected output
```
NO
```