CC + BIT
ruby\nclass BIT\n    def initialize(z) = (@b = [0] * z)\n    def add i\n        while i < @b.size\n            @b[i] += 1\n            i |= i.next\n        end\
```ruby\nclass BIT\n    def initialize(z) = (@b = [0] * z)\n    def add i\n        while i < @b.size\n            @b[i] += 1\n            i |= i.next\n        end\n    end\n    def pref i\n        r = 0\n        while i >= 0\n            r += @b[i]\n            i = (i & i.next).pred\n        end\n        r\n    end\nend\n\ndef result_array a\n    h = a.clone.uniq.sort!.each_with_index.to_h\n    b1, b2 = 2.times.map do\n        b = BIT.new h.size\n        b.add h[a[_1]]\n        b\n    end\n    a1, a2 = [a.shift], [a.shift]\n    ab1, ab2 = [a1, b1], [a2, b2]\n    for x in a\n        t = h[x]\n        case a1.size - b1.pref(t) <=> a2.size - b2.pref(t)\n        when  1; ab1\n        when -1; ab2\n        else\n            a1.size <= a2.size ? ab1 : ab2\n        end .tap { _1 << x; _2.add t }\n    end\n    a1 + a2\nend\n```
['Binary Indexed Tree', 'Ruby']