Clean Segment Tree code TC: O(n log(n)), SC: O(n)
LogicAs element can go upto 10^9, we will compress the data.What is compression data?
Suppose we have 3 elements 100, 23 and 890.We will consider 23 as 1, 100 a
# Logic
<!-- Describe your first thoughts on how to solve this problem. -->
As element can go upto 10^9, we will compress the data.

What is compression data?
Suppose we have 3 elements 100, 23 and 890.

We will consider 23 as 1, 100 as 2 and 890 as 3. 

As there can be 10^5 elements, in compressed data we will have 10^5 elements.

We will use segment tree here.

What does Segment tree range refer?
[left, right] range refers to the number of elements in between left and right inclusive.

Segment Tree will provide insert and getGreaterCount functionality.


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n * log(n))

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n)

# Code
```cpp []
class SegmentTree{
public:
    vector<int> tree;
    int size;
    SegmentTree(int size){
        this->size = size;
        tree.resize(4 * size, 0);
    }
    void insert(int rangeStart, int rangeEnd, int treeIndex, int num){
        if(num < rangeStart || num > rangeEnd){
            return;
        }
        if(rangeStart == rangeEnd){
            tree[treeIndex]++;
            return;
        }
        int mid = (rangeStart + rangeEnd)/2;
        insert(rangeStart, mid, 2 * treeIndex, num);
        insert(mid + 1, rangeEnd, 2 * treeIndex + 1, num);
        tree[treeIndex] = tree[treeIndex * 2] + tree[treeIndex * 2 + 1];
    }
    void insert(int num){
        insert(1, size, 1, num);
    }
    int getGreaterCount(int rangeStart, int rangeEnd, int treeIndex, int num){
        if(num < rangeStart){
            return tree[treeIndex];
        }
        if(rangeEnd <= num){
            return 0;
        }
        int rangeMid = (rangeStart + rangeEnd)/2;
        int leftResult = getGreaterCount(rangeStart, rangeMid, 2 * treeIndex, num);
        int rightResult = getGreaterCount(rangeMid + 1, rangeEnd, 2 * treeIndex + 1, num);
        return leftResult + rightResult;
    }
    int getGreaterCount(int num){
        return getGreaterCount(1, size, 1, num);
    }
};
class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        set<int> uniqueNums;
        for(int num: nums){
            uniqueNums.insert(num);
        }
        int counter = 1;
        map<int, int> compressionMap;
        for(auto& num: uniqueNums){
            compressionMap[num] = counter;
            // cout << "num: " << num << " compressionMap[num]: " << compressionMap[num] << endl;
            counter++;
        }
        SegmentTree segmentTree1(counter), segmentTree2(counter);
        vector<int> arr1 = {nums[0]}, arr2 = {nums[1]};
        segmentTree1.insert(compressionMap[nums[0]]);
        segmentTree2.insert(compressionMap[nums[1]]);
        for(int index = 2; index < nums.size(); index++){
            int num = compressionMap[nums[index]];
            int firstTreeCount = segmentTree1.getGreaterCount(num);
            int secondTreeCount = segmentTree2.getGreaterCount(num);
            // cout << firstTreeCount << " " << secondTreeCount << endl;
            if(firstTreeCount > secondTreeCount){
                arr1.push_back(nums[index]);
                segmentTree1.insert(num);
            }else if(firstTreeCount < secondTreeCount){
                arr2.push_back(nums[index]);
                segmentTree2.insert(num);
            }else{
                if(arr1.size() <= arr2.size()){
                    arr1.push_back(nums[index]);
                    segmentTree1.insert(num);
                }else{
                    arr2.push_back(nums[index]);
                    segmentTree2.insert(num);
                }
            }
        }
        for(int element: arr2){
            arr1.push_back(element);
        }
        return arr1;
    }
};
```
['Segment Tree', 'C++']