set || c++ || O(n*nlog(n)) || 90% fast
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\n\nwe run a nested loop and store answer for j\'th position , the answer at j\'th po
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n\nwe run a nested loop and store answer for j\'th position , the answer at j\'th position denote the answer for all the subarrays starting at that index.\n\nwe start our multiset from the end (nested loop) we check if inserting the current value in the set gives us any disturbance.\ndisturbance ??\ndisturbance is if the next element of the inserted value is greater than 1 and/or the previous element of the newly inserted value is lesser than 1 of it.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nchange happens in two condition ,\nlet x be the elemented to be inserted in the sorted set \n\ncase 1: x is not in bounds of the existing set.\ni.e x is either lesser than minimum element of set or greater\n\n\ncase 2: x is in bounds of the set\n\nwhy does it matter ?\n\nbecause : net change is only valid if the inserted elemented x creates difference with both front and back element.\n\neg:-  set -> { 1,5}\n there is already disturbance between 1 and 5 \n so disturbance is 1\n\nno if we insert 2 into the set we get {1, 2, 5}\neven though the disturbance is now 1 between 2 and 5 , we have eliminated the disturbance between 1 and 5. so net difference is 0\n\nsimililary if we added 3 instead of 2\nwe would get  {1,3,5}\neven though the disturbance 3 has created is 2 , in the process it also has eliminated the disturbance between 1 and 5 \nso the net disturn=bance is now 1 instead of 2.\n\n\nthe third eg is if lets say the set was { 1,3}\nhere we have the disturbance of 1\n\nnow if we add 2 to the set\nwe get {1,2,3}  where the disturbance is of 0\n\nnot only have we not gained any new disturbance we also have removed a previous diturbance.\nthus the net disturbance is -1.\n\n\n\n---\n\nthrough the examples it must be clear that if it is case two we must return curr_disturbance -1 .\n\n\n---\n\n\n   \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n*nlog(n))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int check(multiset<int>&ms,int n){\n        // ms.insert(n);\n        if(ms.find(n)!=ms.end())\n            return 0;\n        \n        \n        int maxi=*ms.rbegin();\n        int mini=*ms.begin();\n        \n        if(n>maxi){\n                    ms.insert(n);\n\n            return n-maxi>1 ? 1:0;\n        }\n        if(n<mini){\n                    ms.insert(n);\n\n            return mini-n>1 ? 1 :0;\n        }\n        \n        auto x=ms.upper_bound(n);\n        int ans=0;\n        if(x!=ms.end()){\n            if(*x -n>1)\n                ans++;\n        }\n        \n        auto y=ms.lower_bound(n);\n        // ya to barabar milega  ->begin , ya to bad ->y\n        \n        if(y!=ms.begin() )\n            if(n- *(--y)>1)\n                ans++;\n        \n        ms.insert(n);\n        \n        return ans-1;\n    }\n    int sumImbalanceNumbers(vector<int>& nums) {\n        vector<int>ans(nums.size());\n        for(int i=nums.size()-1;i>-1;i--){\n            multiset<int>ms;\n            ms.insert(nums[i]);\n            int last=0;\n            for(int j=i-1;j>-1;j--){\n                int x=check(ms,nums[j]);\n             \n\n                ans[j]+=last+x;\n                last+=x;\n            }\n            // break;\n        }\n        \n        int sum=0;\n        for(auto it:ans){\n            sum+=it;\n            // cout<<it<<endl;\n        }\n        \n        return sum;\n    }\n};\n```
['Ordered Set', 'C++']