木雕玩具

不妨设 $a$ 单调递增（无重复），显然如果 $n \leq 3$，答案就是 $0$。

显然答案 $k$ 具有可二分性。也就是说，当 $k < k_0$ 时一定不存在合法的 $x, y, z$，当 $k \geq k_0$ 时一定存在，$k_0$ 就是答案。

因此二分答案，只需要验证答案 $k$ 是否存在合法的 $x, y, z$。

为了覆盖到 $a_1$，且 $x$ 尽量往大取（这样可以覆盖更多的 $a_i$），我们令 $x = a_1 + k$。接下来一段区间的 $a_i$ 会被 $[x-k, x+k]$ 覆盖，我们跳过这段区间，找到下一个未被覆盖的 $a_i$。类似于刚刚的思路，我们令 $y = a_i + k$，再找到下一个未被覆盖的 $a_j$，令 $z = a_j + k$。如果此时所有 $a_i$ 都被覆盖了，那么就合法，否则不合法。

时间复杂度 $O(n \log w)$，其中 $w$ 为值域。