Policy Based Data Structure || C++
Intuition\nA Policy Based Data Structure finds number of elements lesser(or greater) than an element in O(log N) time. The builtin order_of_key function can be 
# Intuition\n**A Policy Based Data Structure finds number of elements lesser(or greater) than an element in ```O(log N)``` time. The builtin ```order_of_key``` function can be used to do so.**\n\n# Approach\n**Using such data structure makes the problem simpler. We would insert the element in it and simply compare the number of elements greater than current element. We would also keep inserting the elements in our final vector to maintain the order of elements and finally inserting from second vector to this vector.**\n\n\n# Code\n```\n\n#include<ext/pb_ds/assoc_container.hpp>\n#include<ext/pb_ds/tree_policy.hpp>\nusing namespace std;\nusing namespace __gnu_pbds;\ntypedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        pbds Q,S;\n        vector<int>f,s;\n        f.push_back(nums[0]);\n        s.push_back(nums[1]);\n        Q.insert(nums[0]); // Keeping track for first vector\n        S.insert(nums[1]); // Keeping track for second vector\n        for(int i=2;i<nums.size();i++){\n            int x=Q.order_of_key(nums[i]);\n            int y=S.order_of_key(nums[i]);\n// x and y would give us the number of elements greater than nums[i] in Q and S\n            if(x>y)Q.insert(nums[i]),f.push_back(nums[i]);\n            else if(y>x)S.insert(nums[i]),s.push_back(nums[i]);\n            else if(x==y){\n                if(Q.size()==S.size())Q.insert(nums[i]),f.push_back(nums[i]);\n                else if(Q.size()>S.size())S.insert(nums[i]),s.push_back(nums[i]);\n                else Q.insert(nums[i]),f.push_back(nums[i]);\n            }\n        }\n        for(int it:s)f.push_back(it);\n        return f;\n    }\n};\n```
['C++']