Editorial covering all approaches.
Solution\n-------\n# Overview\n\nFollowing 1-based indexing, initially, after inserting nums[1] to arr1 and nums[2] to arr2, beginning from index 3, we need to 
# Solution\n-------\n# Overview\n\nFollowing `1-based` indexing, initially, after inserting ```nums[1]``` to ```arr1``` and ```nums[2]``` to ```arr2```, beginning from index 3, we need to distribute the rest of the elements according to the following conditions for every ```nums[i]```:\n* Whichever array has larger number of elements with value greater than ```nums[i]```, append ```nums[i]``` to that array.\n* If that number is same for both the arrays, append the element to the one with less total elements.\n* If there is still a tie, append ```nums[i]``` to ```arr1```\n\nFinally, we need to return an array obtained from merging `arr1` and `arr2` in this order itself.   \n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFollowing exactly what the problem suggests, while traversing from beginning to end, if at every index `i`, we are able to find out the **number of elements greater than** `nums[i]` in each array, we can follow the given conditions and decide whichever array to put `nums[i]` in. \nSo, implementing the ```greaterCount``` function is what we will be majorly following while solving the question itself.\n\n# Algorithm\n1. Declare two empty arrays, `arr1` and `arr2`.\n2. Push ``nums[1]`` and `nums[2]` to `arr1` and `arr2` respectively.\n3. Implement a function `greaterCount` which returns the number of element greater than `nums[i]` in the array `arr`\n4. Traverse the array `nums` starting from index `i = 3`.\n5. For every element `nums[i]`, find the value of `n1` and `n2`, where\n    * `n1 -> greaterCount(arr1, nums[i])`\n    * `n2 -> greaterCount(arr2, nums[i])`\n6. Now, choose the array to insert `nums[i]` into using following conditions:\n    * If `n1 > n2`, insert into `arr1`\n    * If `n2 > n1`, insert into `arr2`\n    * Else if `n1 == n2`:\n        * If `size(arr2) < size(arr1)`, insert into `arr2`\n        * else insert into `arr1`\n7. Finally, declare an array `ans`.\n8. Push all the elements from array `arr1` and then `arr2` into `ans`.\n9. Return the array `ans` as the answer.\n\nNow, we will be discussing several ways to implement and optimize the ```greaterCount``` function.\n# Approach 1: Brute Force (TLE)\n<!-- Describe your approach to solving the problem. -->\nThis is a fairly straightforward approach where we implement the `greaterCount` function using brute force i.e., we traverse the array while counting the number of elements greater than `nums[i]` and then return the same count.\n\n# Implementation\n```CPP []\nclass Solution {\npublic:\n    int greaterCount(vector<int> &arr, int num){\n        int count = 0;\n        for(auto &x:arr)\n            count += (x > num);\n        return count;\n    }\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n        \n        for(int i = 2; i < nums.size(); i++){\n            int n1 = greaterCount(arr1, nums[i]); \n            int n2 = greaterCount(arr2, nums[i]);\n\n            if(n1 > n2)\n                arr1.push_back(nums[i]);\n\n            else if(n1 < n2)\n                arr2.push_back(nums[i]);\n\n            else{\n                if(arr2.size() < arr1.size())\n                    arr2.push_back(nums[i]);\n                else \n                    arr1.push_back(nums[i]);\n            }\n        }\n\n        vector<int> ans;\n        for(auto x:arr1) ans.push_back(x);\n        for(auto x:arr2) ans.push_back(x);\n        \n        return ans;\n    }\n};\n```\n```Python []\nclass Solution:\n    def greater_count(self, arr, num):\n        count = sum(x > num for x in arr)\n        return count\n\n    def resultArray(self, nums):\n        arr1, arr2 = [nums[0]], [nums[1]]\n        \n        for i in range(2, len(nums)):\n            n1 = self.greater_count(arr1, nums[i])\n            n2 = self.greater_count(arr2, nums[i])\n\n            if n1 > n2:\n                arr1.append(nums[i])\n            elif n1 < n2:\n                arr2.append(nums[i])\n            else:\n                if len(arr2) < len(arr1):\n                    arr2.append(nums[i])\n                else:\n                    arr1.append(nums[i])\n\n        return arr1 + arr2\n\n```\n# Complexity\n- Time complexity: `O(N^2)`\nIterating the whole `arr1` and `arr2` in each iteration of `nums` array resulting in `TC => N * N`\nOf course, this being a highly sub-optimal approach will be giving TLE.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N)`\nUsed for storing the `arr1`, `arr2` and `ans` arrays.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Approach 2: Ordered Multiset\n<!-- Describe your approach to solving the problem. -->\nIn this approach, we will be using ordered multisets which can basically return, for any given element, the number of elements that are strictly smaller from the whole set.\nFor the same purpose we can use Data structures like```SortedList``` in Python and ```Ordered Set and GNU C++ PBDS``` in C++. This `Ordered Set` provides two additional features in addition to the already present in the `STL set`:\n`order_of_key(k)`: Number of items strictly smaller than k .\n`find_by_order(k)`: K-th element in a set (counting from zero).\n\nFor reference, you can read more [here](https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/).\n\nUtilizing the same thing, what we will be doing is, calculating the `greaterCount` function in the following way:\n1. First maintain two ordered sets of `arr1` and `arr2` namely, `set1` and `set2`. `Note:` Since, it is possible here to have two same values in the array, we will be using `ordered_multiset` instead, i.e., in C++, while declaring the set we use\n`#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>` -> ordered multiset\ninstead of\n`#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update` -> ordered set\n2. Initially insert `nums[1]` to `set1` and `nums[2]` to `set2`.\n3. Now in the `greaterCount` function, pass the sets themselves instead of the arrays. \n4. In the function, since we have a ordered set of all the elements present in the array and we know we can find the total number of elements strictly smaller than `num` in the following manner:\n    `int elements_strictly_smaller_than_num = set.order_of_key(num);`\nAnd also, number of elements smaller than or equal to `num` would be the same as number of elements strictly smaller than ``(num + 1)``\nSo, `int elements_smaller_or_equal = set.order_of_key(num + 1);`\n5. Finally, the number of elements strictly larger than `num` would be equal to, \n    `int elements_strictly_larger = total - elements_smaller_or_equal;`\nWhich is our required output of the greaterCount function.\n6. After this the question becomes the same as explained in the previous approach with just one minor difference, while pushing the element in any array, we also have to insert it into the respective set.\n\nNow, that we have our optimal `greaterCount` function, we can just following what was discussed earlier for the rest.\n\n# Implementation\n```C++ []\n#include <ext/pb_ds/assoc_container.hpp> \n#include <ext/pb_ds/tree_policy.hpp> \nusing namespace __gnu_pbds;   \n#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> \n\nclass Solution {\npublic:\n    int greaterCount(ordered_multiset &st, int num){\n        int elements_smaller_or_equal_to_num = st.order_of_key(num + 1);\n        int total_elements = st.size();\n\n        return total_elements - elements_smaller_or_equal_to_num;\n    }\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        ordered_multiset set1, set2;\n        set1.insert(nums[0]);\n        set2.insert(nums[1]);\n        \n        for(int i = 2; i < nums.size(); i++){\n            int n1 = greaterCount(set1, nums[i]); \n            int n2 = greaterCount(set2, nums[i]);\n\n            if(n1 > n2)\n                arr1.push_back(nums[i]), set1.insert(nums[i]);\n\n            else if(n1 < n2)\n                arr2.push_back(nums[i]), set2.insert(nums[i]);\n\n            else{\n                if(arr2.size() < arr1.size())\n                    arr2.push_back(nums[i]), set2.insert(nums[i]);\n                else \n                    arr1.push_back(nums[i]), set1.insert(nums[i]);\n            }\n        }\n\n        vector<int> ans;\n        for(auto x:arr1) ans.push_back(x);\n        for(auto x:arr2) ans.push_back(x);\n        \n        return ans;\n    }\n};\n```\n```Python []\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def greater_count(self, sorted_list, num):\n        elements_smaller_or_equal_to_num = sorted_list.bisect_right(num)\n        total_elements = len(sorted_list)\n        return total_elements - elements_smaller_or_equal_to_num\n\n    def resultArray(self, nums):\n        arr1, arr2 = [nums[0]], [nums[1]]\n        set1, set2 = SortedList([nums[0]]), SortedList([nums[1]])\n\n        for i in range(2, len(nums)):\n            n1 = self.greater_count(set1, nums[i])\n            n2 = self.greater_count(set2, nums[i])\n\n            if n1 > n2:\n                arr1.append(nums[i])\n                set1.add(nums[i])\n            elif n1 < n2:\n                arr2.append(nums[i])\n                set2.add(nums[i])\n            else:\n                if len(arr2) < len(arr1):\n                    arr2.append(nums[i])\n                    set2.add(nums[i])\n                else:\n                    arr1.append(nums[i])\n                    set1.add(nums[i])\n\n        return arr1 + arr2\n```\n# Complexity\n- Time complexity: `O(N * log(N))`\nFor each iteration, O(logN) is used to finding the `key` of every `nums[i]` in both the sets. So, total `TC => N * logN`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N)`\nUsed for storing the `set1`, `set2` and `arr1`, `arr2`, `ans` arrays.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Approach 3: Coordinate Compression + Segment Tree\n<!-- Describe your approach to solving the problem. -->\nOne can also think of an approach using Segment Tree in a way that so that each node of the Segment Tree corresponds to a range of values, and the value stored at each node represents the total frequency of values falling within that range in somewhat following manner,\n* `Seg.update(nums[i])` -> updates the frequency of nums[i] by 1 in the tree\n* `Seg.query(nums[i])` -> returns the total number of elements greater than the element `nums[i]` which is also sum of frequencies of all elements between `nums[i]` and the largest element possible. \n\nBoth these things can easily be achieved using a very basic range sum based Segment Tree except there is an issue with this problem. Even though there are a maximum of `n` distinct values possible but the value range is very large, i.e. the given data is not contiguous but really sparse. So, if we\'re using the values directly as indices for Segment Tree nodes, while initializing a normal array based Segment Tree, to accomodate values like `1e9`, we would be needing to allocating an array of size as large as `(4 * 1e9)` which is just not feasible and highly ineffecient since there are only ever going to be at max `n <= 1e5` distinct values.\n\nNow, since here, we only need to find numbers relatively larger than any given number at any point and hence only the relative order of the values matters to us rather than the absolute values themselves, we can actually use a technique called coordinate compression to map the to some contiguous values which still maintain the relative original order.\nIn other words, Compressed coordinates are nothing but a compact representation by assigning contiguous integers to sparse values, preserving information about relative element frequencies and ordering.\nEx: for the array, `nums = [1,5,3,7,2]`, it would be mapped as following\n\n![image.png](https://assets.leetcode.com/users/images/2350251d-b195-476b-bc4e-be628bb2fbba_1711580202.0513694.png)\n\n**Compressing Coordinates Function:** \n1. Create a set to store unique elements from the input array nums.\n2. Assign compressed coordinates (indexes starting from 0) to each unique element by iterating through the set and storing the element along with its compressed index in an unordered map.\n3. Return the unordered map containing the mapping of original elements to their compressed coordinates.\n\nSince there values are contiguous with max map size = `n`, now instead of using the values, we can use their mappings instead and it would be highly efficient and feasible in this case.\n\n**Working of the Segment Tree:**\n1. **Initialization:** Upon initializing the Segment Tree, it\'s constructed to cover the range of compressed coordinates. The tree is implemented using an array where each node corresponds to a particular range of compressed coordinates. Initially, all nodes are initialized with a frequency of 0.\nLet\'s say `sz` is the size of our compressed map.\n2. **Updating Frequencies (Seg.update()):** When updating the Segment Tree with a new element from the input array (nums[i]), we traverse the tree to find the node corresponding to the compressed coordinate of that value and increment its frequency by 1 recusively. This operation effectively updates the frequency count of the element within the Segment Tree.\n3. **Querying Frequencies (Seg.query()):** To find the, total number of elements greater than a particular element (nums[i]), we perform a query operation on the Segment Tree. This involves traversing the tree and summing up the frequencies of all values greater than nums[i] within the compressed coordinate range `[Compressed[nums[i]] + 1, sz - 1]`. \nThe result provides the total count of elements greater than `nums[i]` or rather frequency of elements with compressed indices between in the range `[Compressed[nums[i]] + 1, sz - 1]`.\nRead more about Segment Trees [here](https://cp-algorithms.com/data_structures/segment_tree.html#:~:text=A%20Segment%20Tree%20is%20a,sum%20of%20consecutive%20array%20elements).\n\nFinally, Utilizing this Segment Tree now with compressed values, we will calculate the `greaterCount` in the following way:\n\n1. Compress the values of `nums` array in a unordered_map using the Coordinate_Compression function and store it in a unordered_map say `Compressed`.\n2. Intiailize two Segment Trees `Seg1` and `Seg2` for `arr1` and `arr2` respectively with size equal to the size of the compressedIndices map.\ni.e. `SegmentTree Seg(Compressed.size());`\n3. Since, initially we are inserting `nums[1]` to `arr1` and `nums[2]` to `arr2`, perform the following updates on the Segment trees:\n`Seg1.update(Compressed[nums[1])`-> increasing its frequency by 1 in Seg1\n`Seg2.update(Compressed[nums[2])`-> increasing its frequency by 1 in Seg2\n3. Now in the `greaterCount` function, pass the Segment themselves instead of the arrays. \n4. In the function, to find the number of elements greater than the element `num` in the array, we can just use the query function that we implemented eariler in its respective Segment Tree.\n`int ans = Seg.query(nums[i]);`\nwhich will be the output of our `greaterCount` function.\n6. After this, rest of the question becomes the same as explained in the previous approach with just one minor difference, while insert the element in any array, we also have to increase the frequency of the element\'s compressed coordinate by 1 in that arrays respective Segment Tree.\ni.e., If we insert `nums[i]` into `arr1`, we do the following:\n`Seg1.update(Compressed[nums[i]]);`\n\nNow, that we have our optimal `greaterCount` function, we can just following what was discussed earlier for the rest.\n\n\n# Implementation\n```C++ []\nclass SegmentTree{\n    int n;\n    vector<int> Seg;\n    int query(int i, int sL, int sR, int qL, int qR){\n        if(sL > qR || sR < qL) return 0;\n        if(sL >= qL && sR <= qR) return Seg[i];\n\n        int left_sum = query(2 * i + 1, sL, (sL + sR) / 2, qL, qR);\n        int right_sum = query(2 * i + 2, (sL + sR) / 2 + 1, sR, qL, qR);\n\n        return left_sum + right_sum;\n    }\n    void update(int i, int sL, int sR, int idx){\n        if(sL > idx || sR < idx) return;\n        if(sL == sR){\n            Seg[i]++;\n            return;\n        }\n        int mid = (sL + sR) / 2;\n\n        if(mid >= idx) update(2 * i + 1, sL, mid, idx);\n        else update(2 * i + 2, mid + 1, sR, idx);\n\n        Seg[i] = Seg[2 * i + 1] + Seg[2 * i + 2];\n    }\n    public:\n    SegmentTree(int n){\n        this -> n = n;\n        Seg.resize(4 * n, 0);\n    }\n    int query(int val){\n        return query(0, 0, n - 1, val + 1, n - 1);\n    }\n    void update(int idx){\n        update(0, 0, n - 1, idx);\n    }\n};\nclass Solution {\npublic:\n    unordered_map<int, int> Coordinate_Compression(vector<int> &nums){\n        set<int> st;\n        for(auto x:nums) st.insert(x); \n        unordered_map<int, int> mp;\n        for(auto it:st) mp[it] = mp.size();\n\n        return mp;\n    }\n    int greaterCount(SegmentTree &Seg, int num, unordered_map<int, int> &mp){\n        return Seg.query(mp[num]);\n    }\n    vector<int> resultArray(vector<int>& nums) {\n        unordered_map<int, int> compressedIndices = Coordinate_Compression(nums);\n\n        vector<int> arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        int sz = compressedIndices.size(); //equal to distinct number of elements\n        SegmentTree Seg1(sz), Seg2(sz);\n        Seg1.update(compressedIndices[nums[0]]);\n        Seg2.update(compressedIndices[nums[1]]);\n        \n        for(int i = 2; i < nums.size(); i++){\n            int n1 = greaterCount(Seg1, nums[i], compressedIndices); \n            int n2 = greaterCount(Seg2, nums[i], compressedIndices);\n\n            if(n1 > n2)\n                arr1.push_back(nums[i]), Seg1.update(compressedIndices[nums[i]]);\n\n            else if(n1 < n2)\n                arr2.push_back(nums[i]), Seg2.update(compressedIndices[nums[i]]);\n\n            else{\n                if(arr2.size() < arr1.size())\n                    arr2.push_back(nums[i]), Seg2.update(compressedIndices[nums[i]]);\n                else \n                    arr1.push_back(nums[i]), Seg1.update(compressedIndices[nums[i]]);;\n            }\n        }\n\n        vector<int> ans;\n        for(auto x:arr1) ans.push_back(x);\n        for(auto x:arr2) ans.push_back(x);\n        \n        return ans;\n    }\n};\n```\n```python []\nclass SegmentTree:\n    def __init__(self, n):\n        self.n = n\n        self.Seg = [0] * (4 * n)\n\n    def query(self, i, sL, sR, qL, qR):\n        if sL > qR or sR < qL:\n            return 0\n        if sL >= qL and sR <= qR:\n            return self.Seg[i]\n\n        left_sum = self.query(2 * i + 1, sL, (sL + sR) // 2, qL, qR)\n        right_sum = self.query(2 * i + 2, (sL + sR) // 2 + 1, sR, qL, qR)\n\n        return left_sum + right_sum\n\n    def update(self, i, sL, sR, idx):\n        if sL > idx or sR < idx:\n            return\n        if sL == sR:\n            self.Seg[i] += 1\n            return\n\n        mid = (sL + sR) // 2\n\n        if mid >= idx:\n            self.update(2 * i + 1, sL, mid, idx)\n        else:\n            self.update(2 * i + 2, mid + 1, sR, idx)\n\n        self.Seg[i] = self.Seg[2 * i + 1] + self.Seg[2 * i + 2]\n\n\nclass Solution:\n    def coordinate_compression(self, nums):\n        st = set(nums)\n        mp = {x: i for i, x in enumerate(sorted(st))}\n        return mp\n\n    def greater_count(self, Seg, num, mp):\n        return Seg.query(0, 0, Seg.n - 1, mp[num] + 1, Seg.n - 1)\n\n    def resultArray(self, nums):\n        compressed_indices = self.coordinate_compression(nums)\n\n        arr1, arr2 = [nums[0]], [nums[1]]\n        Seg1, Seg2 = SegmentTree(len(compressed_indices)), SegmentTree(len(compressed_indices))\n        Seg1.update(0, 0, Seg1.n - 1, compressed_indices[nums[0]])\n        Seg2.update(0, 0, Seg2.n - 1, compressed_indices[nums[1]])\n\n        for i in range(2, len(nums)):\n            n1 = self.greater_count(Seg1, nums[i], compressed_indices)\n            n2 = self.greater_count(Seg2, nums[i], compressed_indices)\n\n            if n1 > n2:\n                arr1.append(nums[i])\n                Seg1.update(0, 0, Seg1.n - 1, compressed_indices[nums[i]])\n            elif n1 < n2:\n                arr2.append(nums[i])\n                Seg2.update(0, 0, Seg2.n - 1, compressed_indices[nums[i]])\n            else:\n                if len(arr2) < len(arr1):\n                    arr2.append(nums[i])\n                    Seg2.update(0, 0, Seg2.n - 1, compressed_indices[nums[i]])\n                else:\n                    arr1.append(nums[i])\n                    Seg1.update(0, 0, Seg1.n - 1, compressed_indices[nums[i]])\n\n        ans = arr1 + arr2\n        return ans\n\n```\n# Complexity\n- Time complexity: `O(N * logN)`\nFor each iteration, O(logN) is used process the query of both the arrays (i.e. in the `greaterCount` function). So, total `TC => N * logN`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N)`\nUsed for storing the `Seg1`, `Seg2` Segment trees and `arr1`, `arr2`, `ans` arrays.\n\n# Approach 4: Coordinate Compression + Fenwick Tree (BIT)\n<!-- Describe your approach to solving the problem. -->\nThis approach is very similar to the one with Segment Tree but rather than using Segment Tree to process our queries for `greaterCount` function, we will be using a binary indexed tree. Binary indexed tree will be used here in the following manner: \n* `bit.update(nums[i])` -> updates the frequency of nums[i] by 1 in the tree\n* `bit.query(nums[i])` -> returns the total number of elements greater than the element `nums[i]` which is also sum of frequencies of all elements between `nums[i]` and the largest element possible. \n\nAnd from the very basic implementation of BIT, we can clearly achieve the same. \nOf course, similar to Segment Tree approach, Coordinate Compression is necessary here as well since the data is highly sparse, the range is really big for the elements and we only need the information about relative ordering here.\n\n**Working of the BIT:**\nIt\'s working is almost exactly the same as that of Segment Tree with just the implementation being a little different. Also, BIT is `1-indexed` here.\n1. **Initialization:** On initializing the BIT, the tree is implemented using an array where each node corresponds to a particular range of compressed coordinates. Initially, all nodes are initialized with a frequency of 0.\nLet\'s say `sz` is the size of our compressed map.\n2. **Updating Frequencies (bit.update(idx)):** Increases the value at **idx** by 1 **iteratively**.\n3. **Querying Frequencies (bit.query()):** Returns the sum of frequencies of elements between `[idx + 1, n - 1]` again **itertively**.\nRead more about Binary indexed Trees [here](https://cp-algorithms.com/data_structures/fenwick.html).\n\nRest of the working remains the same as Segment Tree for BIT as well and having obtained and optimal `greaterCount` function, we can just following what was discussed earlier for the rest.\n\n# Implementation\n```C++ []\nclass BIT {\nprivate:\n    vector<int> tree;\n    int n;\npublic:\n    BIT(int size){\n        tree.resize(size + 1, 0);\n        this -> n = size;\n    }\n\n    void update(int idx) {\n        idx++; // since indices in BIT are 1-based\n        while (idx <= n) {\n            tree[idx]++;\n            idx += idx & -idx;\n        }\n    }\n    \n    // Query the sum of values from idx + 1 to n\n    int query(int idx) {\n        return smallerCountQuery(n - 1) - smallerCountQuery(idx);\n    }\n    \n    //returns the sum of values from 0 to idx\n    int smallerCountQuery(int idx){\n        idx++; // since indices in BIT are 1-based\n        int sum = 0;\n        while (idx > 0) {\n            sum += tree[idx];\n            idx -= idx & -idx;\n        }\n        return sum;\n    }\n};\n\nclass Solution {\npublic:\n    unordered_map<int, int> Coordinate_Compression(vector<int> &nums){\n        set<int> st;\n        for(auto x:nums) st.insert(x); \n        unordered_map<int, int> mp;\n        for(auto it:st) mp[it] = mp.size();\n\n        return mp;\n    }\n    int greaterCount(BIT &bit, int num, unordered_map<int, int> &mp){\n        return bit.query(mp[num]);\n    }\n    vector<int> resultArray(vector<int>& nums) {\n        unordered_map<int, int> compressedIndices = Coordinate_Compression(nums);\n\n        vector<int> arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        int sz = compressedIndices.size(); //equal to distinct number of elements\n        BIT bit1(sz), bit2(sz);\n        bit1.update(compressedIndices[nums[0]]);\n        bit2.update(compressedIndices[nums[1]]);\n        \n        for(int i = 2; i < nums.size(); i++){\n            int n1 = greaterCount(bit1, nums[i], compressedIndices); \n            int n2 = greaterCount(bit2, nums[i], compressedIndices);\n\n            if(n1 > n2)\n                arr1.push_back(nums[i]), bit1.update(compressedIndices[nums[i]]);\n\n            else if(n1 < n2)\n                arr2.push_back(nums[i]), bit2.update(compressedIndices[nums[i]]);\n\n            else{\n                if(arr2.size() < arr1.size())\n                    arr2.push_back(nums[i]), bit2.update(compressedIndices[nums[i]]);\n                else \n                    arr1.push_back(nums[i]), bit1.update(compressedIndices[nums[i]]);;\n            }\n        }\n\n        vector<int> ans;\n        for(auto x:arr1) ans.push_back(x);\n        for(auto x:arr2) ans.push_back(x);\n        \n        return ans;\n    }\n};\n```\n```python []\nclass BIT:\n    def __init__(self, size):\n        self.tree = [0] * (size + 1)\n        self.n = size\n\n    def update(self, idx):\n        idx += 1  # Since indices in BIT are 1-based\n        while idx <= self.n:\n            self.tree[idx] += 1\n            idx += idx & -idx\n\n    def smallerCountQuery(self, idx):\n        # returns sum of frequencies between [0 and idx]\n        idx += 1  # Since indices in BIT are 1-based\n        sum = 0\n        while idx > 0:\n            sum += self.tree[idx]\n            idx -= idx & -idx\n        return sum\n\n    def query(self, idx):\n        return self.smallerCountQuery(self.n - 1) - self.smallerCountQuery(idx)\n\nclass Solution:\n    def coordinateCompression(self, nums):\n        st = set(nums)\n        mp = {x: i for i, x in enumerate(sorted(st))}\n        return mp\n\n    def greaterCount(self, bit, num, mp):\n        return bit.query(mp[num])\n\n    def resultArray(self, nums):\n        compressedIndices = self.coordinateCompression(nums)\n\n        arr1 = [nums[0]]\n        arr2 = [nums[1]]\n        \n        sz = len(compressedIndices)\n        \n        bit1 = BIT(sz)\n        bit2 = BIT(sz)\n\n        bit1.update(compressedIndices[nums[0]])\n        bit2.update(compressedIndices[nums[1]])\n\n        for i in range(2, len(nums)):\n            n1 = self.greaterCount(bit1, nums[i], compressedIndices)\n            n2 = self.greaterCount(bit2, nums[i], compressedIndices)\n\n            if n1 > n2:\n                arr1.append(nums[i])\n                bit1.update(compressedIndices[nums[i]])\n            elif n1 < n2:\n                arr2.append(nums[i])\n                bit2.update(compressedIndices[nums[i]])\n            else:\n                if len(arr2) < len(arr1):\n                    arr2.append(nums[i])\n                    bit2.update(compressedIndices[nums[i]])\n                else:\n                    arr1.append(nums[i])\n                    bit1.update(compressedIndices[nums[i]])\n\n        ans = arr1 + arr2\n        return ans\n```\n# Complexity\n- Time complexity: `O(N * logN)`\nFor each iteration, O(logN) is used process the query of both the arrays (i.e. in the `greaterCount` function). So, total `TC => N * logN`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N)`\nUsed for storing the `bit1`, `bit2` Binary Indexed trees and `arr1`, `arr2`, `ans` arrays.\n\n\n\n\n
['Binary Indexed Tree', 'Segment Tree', 'Python', 'C++']