显然 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)\)。