C++ solution | binary Indexed tree
`\n    int query(int id,vector<int>& bin ){\n        int ans = 0;\n        while (id>0){\n            ans+=bin[id];\n            id -= id&-id;\n        }\n     
```\n    int query(int id,vector<int>& bin ){\n        int ans = 0;\n        while (id>0){\n            ans+=bin[id];\n            id -= id&-id;\n        }\n        return ans;\n    }\n    void update(int id,vector<int>& bin,int cnt){\n        \n        \n        while (id<=cnt){\n            bin[id]+=1;\n            id += id&-id;\n        }\n        \n    }\n    vector<int> resultArray(vector<int>& nums) {\n        unordered_map<int,int> umap;\n        set<int> st;\n        for (int i=0;i<nums.size();i++){\n            st.insert(nums[i]);\n        }\n        int cnt = st.size()+1;\n        int num = 1;\n        while (!st.empty()){\n            umap[*st.begin()]= num;\n            num++; st.erase(st.begin());\n        }\n        \n        vector<int> binaryIndex(cnt,0);\n        vector<int> binaryIndex2(cnt,0);\n        cnt--;\n        vector<int> num1;\n        \n        vector<int> num2;\n        num1.push_back(nums[0]);\n        int id1 = umap[nums[0]];\n        update(id1,binaryIndex,cnt);\n        num2.push_back(nums[1]);\n        id1 = umap[nums[1]];\n        update(id1,binaryIndex2,cnt);\n        for (int i=2;i<nums.size();i++){\n            int id = umap[nums[i]];\n            int q1 = query(id,binaryIndex);\n            int q2 = query(id,binaryIndex2);\n            int c1 = query(cnt,binaryIndex)- q1;\n            int c2 = query(cnt,binaryIndex2)-q2;\n            if (c1>c2){\n                num1.push_back(nums[i]);\n                update(id,binaryIndex,cnt);\n            }\n            else if (c1<c2){\n                num2.push_back(nums[i]);\n                update(id,binaryIndex2,cnt);\n            }\n            else {\n                if (num1.size()<=num2.size()){\n                    num1.push_back(nums[i]);\n                update(id,binaryIndex,cnt);\n                }\n                else{\n                   num2.push_back(nums[i]);\n                update(id,binaryIndex2,cnt);\n                }\n            }\n        }\n        vector<int> ans;\n        for (int i=0;i<num1.size();i++){\n            ans.push_back(num1[i]);\n        }\n        for (int i=0;i<num2.size();i++){\n            ans.push_back(num2[i]);\n        }\n        return ans;\n    }``
['Binary Indexed Tree']