G. GCDland Mystical Arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the eccentric town of GCDland, there lives a mathematician named Theo, who has a wild and paranoid conspiracy theory. Theo is convinced that in certain mystical arrays, the greatest common divisor (GCD) of every possible pair of numbers is always the same. He believes that these arrays are messages from an ancient civilization trying to communicate with us through numbers.

Theo's friends think he's gone off the deep end, but he's determined to prove them wrong and uncover the truth behind these arrays. He needs your help to validate his theory. Given an array of integers, your task is to determine whether the GCD of every pair of numbers in the array is indeed the same. If Theo's theory holds true for the given array, you should confirm it; otherwise, you should debunk it.

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

Input

The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 100,000$$$), the number of elements in the array.

The second line contains $$$N$$$ integers $$$A_i$$$ ($$$1 \leq A_i \leq 10^7$$$), the elements of the array.

Output

Print "YES" if the GCD of every pair of numbers in the array is the same. Otherwise, print "NO".

Examples
Input
5
10 2 4 12 15
Output
NO
Input
3
2 4 6
Output
YES
Input
4
2 4 6 8
Output
NO