pbds
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```\n#include<ext/pb_ds/assoc_container.hpp>\nusing namespace __gnu_pbds;\ntypedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        ordered_set s1,s2;\n        vector<int>a,b;\n        a.push_back(nums[0]);\n        b.push_back(nums[1]);\n        s1.insert({nums[0],0});\n        s2.insert({nums[1],1});\n        for(int i=2;i<nums.size();i++){\n            int val=nums[i]+1;\n            int idx1=s1.order_of_key({val,0});\n            int idx2=s2.order_of_key({val,0});\n            int sz1=a.size()-idx1;\n            int sz2=b.size()-idx2;\n            if(sz1>sz2){\n                a.push_back(nums[i]);\n                s1.insert({nums[i],i});\n            }\n            else if(sz2>sz1){\n                b.push_back(nums[i]);\n                s2.insert({nums[i],i});\n            } \n            else if(sz2==sz1){\n                if(a.size()<=b.size()){\n                      a.push_back(nums[i]);\n                s1.insert({nums[i],i});\n                }\n                else {\n                     b.push_back(nums[i]);\n                s2.insert({nums[i],i});\n                }\n            }\n            \n            \n         }\n         vector<int>ans=a;\n         for(auto x : b) ans.push_back(x);\n         return ans;\n\n    }\n};\n```
['Binary Indexed Tree', 'C++']