НОД (наибольший общий делитель) двух целых чисел \(x\) и \(y\) — это такое максимальное целое число \(z\), на которое нацело делятся и \(x\), и \(y\). Например, \(НОД(36, 48) = 12\), \(НОД(5, 10) = 5\), а \(НОД(7,11) = 1\).
У Кристины есть массив \(a\), состоящий ровно из \(n\) целых положительных чисел. Она хочет посчитать НОД каждой соседней пары чисел, чтобы получить новый массив \(b\), называемый НОД-последовательностью.
Таким образом, элементы НОД-последовательности \(b\) будут вычисляться по формуле \(b_i = НОД(a_i, a_{i + 1})\) для \(1 \le i \le n - 1\).
Определите, можно ли удалить из массива \(a\) ровно одно число, чтобы НОД-последовательность \(b\) получилась неубывающей (то есть, всегда было верно \(b_i \le b_{i+1}\))
Например, пусть у Кристины был массив \(a\) = [\(20, 6, 12, 3, 48, 36\)]. Если она удалит из него \(a_4 = 3\) и посчитает НОД-последовательность \(b\), то получит:
- \(b_1 = НОД(20, 6) = 2\)
- \(b_2 = НОД(6, 12) = 6\)
- \(b_3 = НОД(12, 48) = 12\)
- \(b_4 = НОД(48, 36) = 12\)
Полученная НОД-последовательность
\(b\) = [
\(2,6,12,12\)] является неубывающей, так как
\(b_1 \le b_2 \le b_3 \le b_4\).
Выходные данные
Выведите:
- «YES», если можно удалить из массива \(a\) ровно одно число так, чтобы НОД-последовательность \(b\) получилась неубывающей;
- «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).