累積最大値を追跡し、それを 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 は非減少である。また aia_iai は最大値に含まれる項だから Mi≥aiM_i \ge a_iMi≥ai であり、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 となる。