PBDS approach
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: O(N logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <ext/pb_ds/assoc_container.hpp> // Common file\nusing namespace __gnu_pbds;\n#define pb push_back\ntypedef tree<pair<int,int>,null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> res1;\n        indexed_set s1;\n        indexed_set s2;\n        vector<int> res2;\n        res1.pb(nums[0]);\n        res2.pb(nums[1]);\n        s1.insert({nums[0],0});\n        s2.insert({nums[1],1});\n\n        for(int i=2;i<nums.size();i++){\n            int f1=s1.size()-s1.order_of_key({nums[i]+1,0});\n            int f2=s2.size()-s2.order_of_key({nums[i]+1,0});\n            // cout<<"For e= "<<nums[i]<<" No of greater ele in arr1: "<<f1<<" No of greater ele in arr2: "<<f2<<endl;\n            if(f1>f2){\n                res1.pb(nums[i]);\n                s1.insert({nums[i],i});\n            }\n            else if(f1<f2){\n                res2.pb(nums[i]);\n                s2.insert({nums[i],i});\n            }\n            else{\n                //f1==f2\n                if(res1.size()>res2.size()){\n                    res2.pb(nums[i]);\n                    s2.insert({nums[i],i});\n                }\n                else{\n                    res1.pb(nums[i]);\n                    s1.insert({nums[i],i});\n                }\n            }\n        }\n        res1.insert(res1.end(),res2.begin(),res2.end());\n\n        return res1;\n    }\n};\n```
['C++']