显然 gcd > 1 等价于枚举一个数，使得所有数都是这个数的倍数，进一步可以规约到枚举质因数。
如果确定了质因数，我们很好用 DP 做到 \(O(n)\) 的复杂度，但问题就是质因数的规模确实不小。
有一个结论是，只需要枚举 \(a_1, a_1 + 1, a_1 - 1, a_n, a_n + 1, a_n - 1\) 的质因数即可。
因为你发现，如果质因数不在这个里面，意味着它肯定要把 \(a_1, a_n\) 都删掉，这样就不符合只能删除长度 $ < n$ 的区间的规定，所以 \(a_1, a_n\) 必有一个数不会删掉，因此将规模缩小到 \(O(1)\) 级别，复杂度 \(O(n)\)。