Python: sortedContainers < 20 lines. O(n \log n)
Intuition\nThe question boils down to implement efficient operations:\n \n - append value to an array\n - find number of elements >= x\n\nIn Python sorted conta
# Intuition\nThe question boils down to implement efficient operations:\n \n - append value to an array\n - find number of elements >= x\n\nIn Python [sorted containers](https://grantjenks.com/docs/sortedcontainers/) allows both of those operations in $O(\\log n)$.\nSo the solution is very easy.\n\n\n-----------\n\nWhat if you do not have sorted containers? Then both such questions are answered with Binary Indexed Tree. See [cp-algorithms](https://cp-algorithms.com/data_structures/fenwick.html) for a detailed explanation \n\n# Complexity\n- Time complexity: $O(n \\log n)$\n- Space complexity: $O(n)$\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n  def resultArray(self, nums: List[int]) -> List[int]:\n    sc1, sc2 = SortedList([nums[0]]), SortedList([nums[1]])\n    arr1, arr2 = [nums[0]], [nums[1]]\n    for i in range(2, len(nums)):\n      cnt1 = len(sc1) - sc1.bisect_right(nums[i])\n      cnt2 = len(sc2) - sc2.bisect_right(nums[i])\n\n      if cnt1 > cnt2:\n        sc1.add(nums[i])\n        arr1.append(nums[i])\n      elif cnt1 < cnt2:\n        sc2.add(nums[i])\n        arr2.append(nums[i])\n      elif len(sc1) <= len(sc2):\n        sc1.add(nums[i])\n        arr1.append(nums[i])\n      else:\n        sc2.add(nums[i])\n        arr2.append(nums[i])\n\n    return arr1 + arr2\n```
['Python']