問題

考察の流れ

ある $X$ を選んだとき， $a_i =X$ となる $i$ の個数を最大化する．

まず， $X$ を固定した場合． $a_i =X$ となる $i$ の個数を最大化するには，数列中の全ての $X-1$ に+1，全ての $X+1$ に-1してあげればいい．

そして， $X$ として何を選べば $a_i =X$ となる $i$ の個数を最大化できるかについては， $X$ として考えられる値を全て調べてあげればいい．各 $X$ に対し，数列中の $X-1$ ， $X$ ， $X+1$ の個数の和を出してあげてそれが最大となる $X$ を探す．数列中の $X-1$ ， $X$ ， $X+1$ の個数の和を出す処理は，数列をあらかじめソートしておいて二分探索することでO(log N)で可能となる．