概要

問題の条件を整理して簡単にしてみましょう．

問題原案：uni_kakurenbo

解説

整数 $a$ についての条件 $|a - x| \leq K$ を考えます．

数直線をイメージするとよいです．
これは，$x$ を中央とした幅が $2K$ の閉区間に $a$ が含まれることと等しいです．

整数 $l$ に対して， $l \leq i < r$ なる任意の整数 $i$ について $A_i$ が上記の条件を満たすような $x$ が存在する最大の整数 $r$ を $R_l$ とします．

$A = (A_1, A_2, \ldots, A_N)$ を昇順に並び替えると，$R_l$ は $l$ に関して広義単調増加となりますから，尺取り法の要領で $l$ の昇順に $R_l$ を求めることができます．

このとき，$R_l - l$ の最大値が答えです．

解説：uni_kakurenbo

実装例