c++ solution using fenwick tree( binary index tree)
\nclass Solution {\npublic:\n    int N;\n    void update(int i,int val,vector<int>&bit)\n    {\n        while(i<N)\n        {\n            bit[i]+=val;\n       
```\nclass Solution {\npublic:\n    int N;\n    void update(int i,int val,vector<int>&bit)\n    {\n        while(i<N)\n        {\n            bit[i]+=val;\n            i+=(i&-i);\n        }\n    }\n    int find(int i,vector<int>&bit)\n    {\n        int sum=0;\n        while(i>0)\n        {\n            sum+=bit[i];\n            i-=(i&-i);\n        }\n        return sum;\n    }\n    vector<int> resultArray(vector<int>& nums) \n    {\n        N=nums.size()+5;\n        vector<int>bit1(N,0),bit2(N,0);\n        vector<int>arr1,arr2;\n        vector<int>temp=nums;\n        sort(temp.begin(),temp.end());\n        map<int,int>mp;\n        for(int i=0;i<temp.size();i++)\n        {\n            mp[temp[i]]=i+1;\n        }\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n        update(mp[nums[0]],1,bit1);\n        update(mp[nums[1]],1,bit2);\n        for(int i=2;i<nums.size();i++)\n        {\n            int greaterCount1=arr1.size()-find(mp[nums[i]],bit1);\n            int greaterCount2=arr2.size()-find(mp[nums[i]],bit2);\n            if(greaterCount1>greaterCount2)\n            {\n                arr1.push_back(nums[i]);\n                update(mp[nums[i]],1,bit1);\n            }\n            else if(greaterCount1<greaterCount2)\n            {\n                arr2.push_back(nums[i]);\n                update(mp[nums[i]],1,bit2);\n            }\n            else\n            {\n                if(arr1.size()<arr2.size())\n                {\n                    arr1.push_back(nums[i]);\n                    update(mp[nums[i]],1,bit1);\n                }\n                else if(arr1.size()>arr2.size())\n                {\n                    arr2.push_back(nums[i]);\n                    update(mp[nums[i]],1,bit2);\n                }\n                else{\n                    arr1.push_back(nums[i]);\n                    update(mp[nums[i]],1,bit1);\n                }\n            }\n        }\n        for(auto &it:arr2) arr1.push_back(it);\n        return arr1;\n    }\n};\n```
['C', 'C++']