Вам задан массив \(a_1, a_2, \dots, a_n\), в котором все \(a_i\) — целые и больше \(0\).
За одну операцию вы можете выбрать две различные позиции \(i\) и \(j\) (\(1 \le i, j \le n\)). Если \(gcd(a_i, a_j)\) равен минимуму всего массива \(a\), то вы можете поменять местами \(a_i\) и \(a_j\). \(gcd(x, y)\) означает наибольших общий делитель (НОД) чисел \(x\) и \(y\).
Вам нужно сделать массив \(a\) неубывающим, используя заданную операцию произвольное количество раз (возможно, ни разу). Определите, возможно ли это.
Массив \(a\) — неубывающий, тогда и только тогда, когда \(a_1 \le a_2 \le \ldots \le a_n\).
Выходные данные
Для каждого набора, выведите «YES», если возможно сделать массив \(a\) неубывающим, используя описанную выше операцию, или «NO» в противном случае.
Примечание
В первом и третьем наборах, массив уже неубывающий.
Во втором наборе, мы можем сначала свапнуть \(a_1\) и \(a_3\), а потом \(a_1\) и \(a_5\), и получим неубывающий массив.
В четвертом наборе, невозможно сделать массив неубывающим, используя заданную операцию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4
|
YES
YES
YES
NO
|