Elimination via GCD Operations

You are given a sequence of n integers \(a_1,a_2,\dots,a_n\). An operation is defined as follows:

• Select three distinct indices \(x,y,z\) (each in \([1,n]\)) such that \[ \gcd(a_x, a_y)=a_z. \]
• Then eliminate \(a_z\) (i.e. it can no longer be used in any subsequent operation).

The task is to determine whether it is possible, through a sequence of these operations, to eliminate exactly \(n-2\) numbers from the array. In other words, can you perform several operations so that only two numbers remain?

Note: All numbers in the sequence are positive integers. In each operation the indices \(x,y,z\) must all be different.

Observation and Hint: A key observation is that if you denote \(G=\gcd(a_1,a_2,\dots,a_n)\), then in any valid operation the eliminated number \(a_z\) equals \(\gcd(a_x,a_y)\) which is always a multiple of \(G\). In many cases, it turns out that only elements equal to \(G\) can be eliminated without jeopardizing future operations. In particular, it can be shown that:

• If \(n = 3\), the answer is "Yes" provided that at least one element equals \(G\);
• If \(n \ge 4\), the answer is "Yes" if and only if at least two elements in the sequence are equal to \(G\); otherwise, the answer is "No".

Based on this observation, you are to decide whether it is possible to eliminate \(n-2\) numbers from the sequence.

inputFormat

The first line contains a single integer \(n\) (with \(n \geq 3\)). The second line contains \(n\) space‐separated positive integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output a single line containing either Yes or No indicating whether it is possible to perform the operations so that exactly \(n-2\) numbers are eliminated.

sample

3
2 4 6

Yes