Simple Ordered Set  Solution in C++
Intuition\n Describe your first thoughts on how to solve this problem. \nAs we have to maintain sorted order and also have to  find the element in middle in at 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs we have to maintain sorted order and also have to  find the element in middle in at most Logn time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor maintaining values sorted and find element by index we have a direct **Data structure Ordered Set** but in we have to maintain a Ordered set that also contain duplicate value.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(Logn)$$ for every Add and Median operation \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nTotal number of add elements = $$O(N)$$\n# Code\n```\n\n#include <ext/pb_ds/assoc_container.hpp> \n#include <ext/pb_ds/tree_policy.hpp>\nusing namespace __gnu_pbds;\ntypedef tree<pair<int,int>, null_type, \n        less<pair<int,int>>, rb_tree_tag,\n        tree_order_statistics_node_update>\n        ordered_set_pair;\n  \nclass MedianFinder {\npublic:\n    ordered_set_pair st;\n    int a=0;\n    MedianFinder() {\n        \n    }\n    \n    void addNum(int num) {\n        //insert pair to store duplicate value in Ordered Set\n        st.insert({num,a++});\n    }\n   \n    double findMedian() { \n        int n=st.size();\n        auto itr = st.find_by_order(n/2); \n        double num= (*itr).first;\n        if(n%2==0){\n            auto itr2=st.find_by_order((n-1)/2);\n            double num1=(*itr2).first;\n            num=(num+num1)/2;\n        }\n        return num;\n        \n    }\n};\n\n```\n\n\n\n
['Ordered Set', 'C++']