寻找最大的回文余数数组

有一个长度为 $n$ 的非负整数数组 $a$，定义 $f(a,x)=[a_1 \mod x,a_2 \mod x,\dots,a_n \mod x]$，求最大的 $x$，使得 $f(a,x)$ 是一个回文数组。

首先考虑 $x$ 的范围。由于 $0 \le a_i \le 10^9$，所以 $x$ 最大也只能是 $10^9$。但是，当 $x$ 大于等于 $n$ 时，$f(a,x)$ 的长度只有 $n$，不可能是回文的，所以 $x$ 最大只能是 $\min(n,10^9)$。

接下来考虑如何判断 $f(a,x)$ 是否是回文的。一个简单的方法是将 $f(a,x)$ 的前一半和后一半分别反转，然后判断它们是否相等。但是，这个方法需要开辟额外的空间，空间复杂度是 $O(n)$，不符合题目的空间限制。

考虑用双指针来判断。设 $i$ 和 $j$ 分别指向 $f(a,x)$ 的首尾两个元素。如果 $i$ 和 $j$ 指向的元素相等，就将 $i$ 和 $j$ 向中间移动；否则，$f(a,x)$ 不是回文的。

时间复杂度 $O(n \log n)$，因为需要对 $x$ 进行二分搜索。

代码实现

注意处理 $x$ 为 $0$ 和 $1$ 的情况，以及 $x$ 可能超过 $\min(n,10^9)$ 的情况。