https://atcoder.jp/contests/abc094/tasks/arc095_a
まず、具体例で考えてみる。aがソートされている場合を考えよう。
1,2,3,4,5
で左からi番目の数を取り除いた中央値を考えると
3,3,2,2,2
となる。
1,2,2,3
であれば
2,2,2
である。
よって、pos = floor((l+1)/2), 取り除かれた値をxとすると、
- l が偶数の時
- x ≤ a[pos] -> 取り除いた後は a[pos+1] が中央値
- x > a[pos] -> a[pos]
- l が奇数の時
- x < a[pos] -> a[pos]
- x ≥ a[pos] -> a[pos-1]
であることがわかる。