Reorder Array to Achieve Adjacent GCD One

Given an array of positive integers, determine whether it is possible to reorder its elements so that the greatest common divisor (GCD) of every adjacent pair is 1. In other words, if the sequence is a1, a2, ..., an, then for each i (1 ≤ i < n), (\gcd(a_i, a_{i+1}) = 1). If such a reordering exists, print YES; otherwise, print NO.

It is guaranteed that the input array is small enough to allow an exhaustive search through all possible reorderings.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated positive integers representing the elements of the array.

outputFormat

Output a single line to standard output (stdout) containing either YES if there exists a reordering of the array such that every adjacent pair of numbers has a GCD of 1, or NO if no such reordering exists.## sample

6
14 3 2 5 9 6

YES