C++ solution using binary indexed tree
Code\n\nclass Solution {\npublic:\n    map<int, int>mp;\n    int bit1[100005], bit2[100005];\n    int n;\n\n    void update(int index, int x, int num){\n       
# Code\n```\nclass Solution {\npublic:\n    map<int, int>mp;\n    int bit1[100005], bit2[100005];\n    int n;\n\n    void update(int index, int x, int num){\n        for(;index<n;index+=(index&-index)){\n            if(num == 1)\n                bit1[index]+=x;\n            else\n                bit2[index]+=x;\n        }\n    }\n\n    int sum(int index, int num){\n        int res = 0;\n        for(;index>0;index-=(index&-index)){\n            if(num == 1)\n                res+=bit1[index];\n            else\n                res+=bit2[index];\n        }\n        return res;\n    }\n\n\n    vector<int> resultArray(vector<int>& nums) {\n        set<int>temp(nums.begin(), nums.end());\n        int index = 1;\n\n        for(auto it: temp){\n            mp[it] = index;\n            ++index;\n        }\n\n        n = 100004;\n\n        vector<int>arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        update(mp[nums[0]], 1, 1);\n        update(mp[nums[1]], 1, 2);\n\n        for(int i=2;i<nums.size();i++){\n            int greaterCnt1 = sum(n, 1) - sum(mp[nums[i]], 1);\n            int greaterCnt2 = sum(n, 2) - sum(mp[nums[i]], 2);\n\n            if(greaterCnt1 > greaterCnt2){\n                arr1.push_back(nums[i]);\n                update(mp[nums[i]], 1, 1);\n            }\n            else if(greaterCnt1 < greaterCnt2){\n                arr2.push_back(nums[i]);\n                update(mp[nums[i]], 1, 2);\n            }\n            else{\n                if(arr1.size() > arr2.size()){\n                    arr2.push_back(nums[i]);\n                    update(mp[nums[i]], 1, 2);\n                }\n                else if(arr1.size() <= arr2.size()){\n                    arr1.push_back(nums[i]);\n                    update(mp[nums[i]], 1, 1);\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++']