Beautiful Array

Given an array of n integers, determine whether the array is beautiful. An array is considered beautiful if for every pair of elements a_i and a_j (with 1 ≤ i < j ≤ n), either a_i divides a_j or a_j divides a_i.

The divisibility condition must hold for all distinct pairs in the array. This problem requires careful checking of all pairs after sorting the array.

Example: For the array [4, 8, 16], since 4 divides 8 and 8 divides 16 (and transitively, 4 divides 16), the array is beautiful. On the other hand, the array [5, 10, 15, 20] is not beautiful because 5 does not divide 15 (nor does 15 divide 5).

inputFormat

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array.

The second line contains n space-separated integers, where each integer a_i satisfies 1 ≤ a_i ≤ 10⁹.

outputFormat

Output a single line containing YES if the array is beautiful, and NO otherwise.

3
4 8 16

YES