\(1\) つの要素があまりを取ると元の値のままか半分以下になるので, その要素が半分以下になるのは \(\log N\) 回以下である.

よって, 優先順位つきキューに入れておいて \(X_i\) 以上ならあまりを取って入れ直すのを繰り返す.