Maintain two sorted list, and then binary search on them to find out GreaterCount
Intuition\nIn this question, we should focus on optimizing GreaterCount function, otherwise everything is same as problem #3069.\n\n# Approach\n- To get number 
# Intuition\nIn this question, we should focus on optimizing GreaterCount function, otherwise everything is same as problem #3069.\n\n# Approach\n- To get number of elements greater than a given element, easiest way is to do a binary search. But to do binary search, list has to be sorted.\n- So we maintain two sorted lists for arr1 & arr2 and then binary search on them to find out GreaterCount. Also maintain two normal lists arr1l and arr2l which would be used later for concatenating for answer.\n- After we have GreaterCount, then it is easy, just follow the instructions in question.\n\n# Complexity\n- Time complexity: O(n^2 logn)\n- Space complexity: O(n)\n\n# Code\n```\npublic class Solution {\n    public int[] ResultArray(int[] nums) {\n        var n = nums.Length;\n        var comparer = new DuplicateKeyComparer<int>();\n        SortedList<int,int> arr1 = new SortedList<int,int>(comparer), arr2 = new SortedList<int,int>(comparer);\n        List<int> arr1l = new List<int>(), arr2l = new List<int>();\n        \n        arr1.Add(nums[0],nums[0]);  arr1l.Add(nums[0]);\n        arr2.Add(nums[1],nums[1]);  arr2l.Add(nums[1]);\n        \n        for(var i=2; i<n; i++){\n            int arr1gc = GreaterCount(arr1, nums[i]), arr2gc = GreaterCount(arr2, nums[i]);\n            \n            if(arr1gc > arr2gc) {\n                arr1.Add(nums[i],nums[i]); \n                arr1l.Add(nums[i]); \n            }\n            else if(arr2gc > arr1gc) { \n                arr2.Add(nums[i],nums[i]); \n                arr2l.Add(nums[i]);  \n            }\n            else if(arr2.Count < arr1.Count) { \n                arr2.Add(nums[i],nums[i]); \n                arr2l.Add(nums[i]);  \n            }\n            else {\n                arr1.Add(nums[i],nums[i]);\n                arr1l.Add(nums[i]);  \n            }\n        }\n        return arr1l.Concat(arr2l).ToArray();\n    }\n    \n    private int GreaterCount(SortedList<int,int> lst, int val){\n        int l = 0;\n        int size = lst.Count;\n        int r = size-1;\n        int resultantIndex = size;\n        while(l<=r){\n            int mid = l + (r-l) / 2;\n            if(lst.Values[mid] <= val){\n                l = mid +1;\n            }\n            else{\n                r = mid -1;\n                resultantIndex = mid;\n            }\n        }\n        return (size-resultantIndex);\n    }\n}\n\npublic class DuplicateKeyComparer<TKey> :IComparer<TKey> where TKey : IComparable\n{\n    public int Compare(TKey x, TKey y)\n    {\n        int result = x.CompareTo(y);\n        if (result == 0) return 1; // Handle equality as being greater.\n        return result;\n    }\n}\n```
['Binary Search', 'Ordered Set', 'C#']