💥💥 Beats 100% on runtime and memory [EXPLAINED]
IntuitionI first use a Segment Tree to efficiently track the count of elements in the range of the array. This helps me quickly check how many elements are grea
# Intuition
I first use a Segment Tree to efficiently track the count of elements in the range of the array. This helps me quickly check how many elements are greater than the current element when comparing between two potential subarrays. To handle duplicates, I use Coordinate Compression to map each unique value in the array to a smaller range, making it easier for the segment tree to process.

# Approach
The approach is straightforward: I maintain two subarrays, updating them based on comparisons made with the segment tree's queries. If the counts of greater elements are equal, I decide based on the size of the subarrays, adding the element to the smaller one.

# Complexity
- Time complexity:
O(n log n) due to the segment tree updates and queries, where n is the length of the input array.

- Space complexity:
O(n) because of the segment tree and the coordinate compression map.

# Code
```kotlin []
class Solution {

    class SegmentTree(private val n: Int) {
        private val tree = IntArray(4 * n)

        fun update(index: Int, value: Int, node: Int, left: Int, right: Int) {
            if (left == right) {
                tree[node] = tree[node] + 1
                return
            }
            val mid = (left + right) / 2
            if (index <= mid) {
                update(index, value, 2 * node, left, mid)
            } else {
                update(index, value, 2 * node + 1, mid + 1, right)
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1]
        }

        fun query(qleft: Int, qright: Int, node: Int, left: Int, right: Int): Int {
            if (qleft > right || qright < left) return 0

            if (qleft <= left && qright >= right) {
                return tree[node]
            }
            val mid = (left + right) / 2
            val leftCount = query(qleft, qright, 2 * node, left, mid)
            val rightCount = query(qleft, qright, 2 * node + 1, mid + 1, right)
            return leftCount + rightCount
        }
    }

    fun resultArray(nums: IntArray): IntArray {
        val set = sortedSetOf<Int>()
        nums.forEach { set.add(it) }

        val n = nums.size
        val max = set.size
        val map = mutableMapOf<Int, Int>()
        var idx = 1
        for (num in set) map[num] = idx++

        val arr1 = IntArray(n)
        val arr2 = IntArray(n)

        val tree01 = SegmentTree(max)
        val tree02 = SegmentTree(max)

        arr1[0] = nums[0]
        tree01.update(map[nums[0]]!!, 1, 1, 1, max)
        arr2[0] = nums[1]
        tree02.update(map[nums[1]]!!, 1, 1, 1, max)

        var idx1 = 0
        var idx2 = 0

        for (i in 2 until nums.size) {
            val count01 = tree01.query(map[nums[i]]!! + 1, max, 1, 1, max)
            val count02 = tree02.query(map[nums[i]]!! + 1, max, 1, 1, max)

            var arr01added = count01 == count02 && (idx1 == idx2 || idx1 < idx2)
            arr01added = arr01added || (count01 > count02)

            if (arr01added) {
                arr1[++idx1] = nums[i]
                tree01.update(map[nums[i]]!!, 1, 1, 1, max)
            } else {
                arr2[++idx2] = nums[i]
                tree02.update(map[nums[i]]!!, 1, 1, 1, max)
            }
        }

        val ans = IntArray(n)
        for (i in idx1 downTo 0) ans[i] = arr1[i]
        for (i in nums.size - 1 downTo idx1 + 1) ans[i] = arr2[i - (idx1 + 1)]

        return ans
    }
}

```
['Array', 'Binary Search', 'Bit Manipulation', 'Binary Indexed Tree', 'Segment Tree', 'Binary Search Tree', 'Simulation', 'Binary Tree', 'Kotlin']