Fenwick tree with coordinate compression [python]
Approach\nWe just need to support count greater operation fast, to do this we can use fenwick trees. Fenwick tree supports add and find_prefix_sum operation in 
# Approach\nWe just need to support count greater operation fast, to do this we can use fenwick trees. Fenwick tree supports add and find_prefix_sum operation in logn time. We increment the index of the number we have seen by 1 for each number added, to compute prefix_sum_x is then the count of elements <=x.\n\nFenwick tree requires O(max_element) size. To reduce this, we apply coordinate compression. \n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    lim = 10**5+5\n    id_mapper = None\n    el_mapper = None\n    fen1 = None\n    fen2 = None\n\n    def coordinate_compress(self, nums: List[int]):\n        uniq = list(set(nums))\n        uniq = sorted(uniq)\n        self.id_mapper = {}\n        self.el_mapper = {}\n        for i, x in enumerate(uniq):\n            self.id_mapper[x] = i+1\n        for i, x in enumerate(nums):\n            nums[i] = self.id_mapper[nums[i]]\n        for k, v in self.id_mapper.items():\n            self.el_mapper[v] = k\n    \n    def increment(self, id, fen):\n        while id < self.lim:\n            fen[id] += 1\n            id += id&-id\n    \n    def query(self, id, fen):\n        ans = 0\n        while id>0:\n            ans += fen[id]\n            id -= id&-id\n        return ans\n\n    def resultArray(self, nums: List[int]) -> List[int]:\n        self.coordinate_compress(nums)\n        self.fen1 = [0]*self.lim\n        self.fen2 = [0]*self.lim\n        \n        arr1 = [nums[0]]\n        self.increment(arr1[0], self.fen1)\n        arr2 = [nums[1]]\n        self.increment(arr2[0], self.fen2)\n        nums = nums[2:]\n        for num in nums:\n            gt1 = len(arr1) - self.query(num, self.fen1)\n            gt2 = len(arr2) - self.query(num, self.fen2)\n            if gt1>gt2:\n                arr1.append(num)\n                self.increment(num, self.fen1)\n            elif gt1<gt2:\n                arr2.append(num)\n                self.increment(num, self.fen2)\n            elif len(arr1) < len(arr2):\n                arr1.append(num)\n                self.increment(num, self.fen1)\n            elif len(arr1) > len(arr2):\n                arr2.append(num)\n                self.increment(num, self.fen2)\n            else:\n                arr1.append(num)\n                self.increment(num, self.fen1)\n        arr1.extend(arr2)\n        for i, x in enumerate(arr1):\n            arr1[i] = self.el_mapper[x]\n        return arr1\n\n```
['Python3']