跟踪前缀最大值并将其下移 d2\dfrac{d}{2}2d，得到一个非递减数列，其与 aia_iai 的距离由 di≤dd_i \le ddi≤d 控制。
定义 Mi=max{aj:1≤j≤i}M_i = \max\{a_j : 1 \le j \le i\}Mi=max{aj:1≤j≤i}，xi=Mi−d2x_i = M_i - \dfrac{d}{2}xi=Mi−2d。由于 Mi≤Mi+1M_i \le M_{i+1}Mi≤Mi+1，数列 x1≤x2≤⋯≤xnx_1 \le x_2 \le \cdots \le x_nx1≤x2≤⋯≤xn 非递减。此外 Mi≥aiM_i \ge a_iMi≥ai（因为 aia_iai 是最大值中的一项），且 Mi−ai≤Mi−min{aj:i≤j≤n}=di≤dM_i - a_i \le M_i - \min\{a_j : i \le j \le n\} = d_i \le dMi−ai≤Mi−min{aj:i≤j≤n}=di≤d，所以对每个 iii 都有 0≤Mi−ai≤d0 \le M_i - a_i \le d0≤Mi−ai≤d。