Easy BIT solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass BIT{\npublic:\n    int sz;\n    vector<int> val;\n    BIT(int n) {\n        sz = n;\n        val = vector<int>(n+1,0);\n    }\n    int get(int x){\n        int result = 0;\n        while(x > 0) {\n            result += val[x];\n            x = x - (x & (-x));\n        }\n        return result;\n    }\n\n    void add(int x) {\n        while(x <= sz) {\n            val[x] += 1;\n            x = x + (x & (-x));\n        }\n    }\n};\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        set<int> tmp(nums.begin(), nums.end());\n        unordered_map<int,int> mp;\n        int idx = 1;\n        for(auto it : tmp)\n            mp[it] = idx++;\n        int sz = nums.size();\n        BIT bt1(sz);\n        BIT bt2(sz);\n        vector<int> arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n        bt1.add(mp[nums[0]]);\n        bt2.add(mp[nums[1]]);\n        for(int i = 2; i < nums.size(); i++) {\n            int g1 = arr1.size() - bt1.get(mp[nums[i]]);\n            int g2 = arr2.size() - bt2.get(mp[nums[i]]);\n            if(g1 > g2) {\n                arr1.push_back(nums[i]);\n                bt1.add(mp[nums[i]]);\n            } else if(g1 < g2) {\n                arr2.push_back(nums[i]);\n                bt2.add(mp[nums[i]]);\n            } else {\n                if(arr1.size() > arr2.size()){\n                    arr2.push_back(nums[i]);\n                    bt2.add(mp[nums[i]]);\n                }\n                else if(arr1.size() <= arr2.size()){\n                    arr1.push_back(nums[i]);\n                    bt1.add(mp[nums[i]]);\n                }\n            }\n        }\n\n        vector<int>res;\n        for(auto it: arr1)\n            res.push_back(it);\n        \n        for(auto it: arr2)\n            res.push_back(it);\n        \n\n        return res;\n    }\n};\n```
['Binary Indexed Tree', 'C++']