Explained; SegmentTree approach + beat 100% with compact Fenwick
Intuition\nWe need to efficiently count elements greater than a given value in both arrays. Using two arrays and scanning them each time would be O(n) per query
# Intuition\nWe need to efficiently count elements greater than a given value in both arrays. Using two arrays and scanning them each time would be O(n) per query. A segment tree can do this in O(log n).\n\n(Also see bonus at the very end: compact Fenwick approach to beat 100%)\n\n# Approach\n1. Coordinate compression: Map original values to compressed indices 0..k to make segment tree operations efficient\n   - Sort values and assign ranks while preserving original indices\n   - Equal values get same rank\n\n2. Use two segment trees to track frequency of compressed values in each array\n   - Each tree node stores count of elements in its range\n   - Query range [val+1, max_val] gives count of elements > val\n\n3. Process elements sequentially:\n   - First two elements go to arr1 and arr2 respectively\n   - For each remaining element:\n     1. Query both trees for elements greater than current value\n     2. Add to array with higher count (or follow tiebreak rules)\n     3. Update corresponding tree with new element\n\n# Complexity\n- Time complexity: O(n log n)\n\n- Space complexity: O(n)\n\n# Code\n\n```kotlin []\n// Segment tree implementation for range queries\nclass SegT(private val N: Int) {\n    private val root = 1\n    private val data: IntArray\n    \n    init {\n        data = IntArray(2 * nxpow(N))\n    }\n    \n    // Find next power of 2 >= N\n    private fun nxpow(N: Int): Int {\n        var r = 1\n        while (true) {\n            if (r >= N) return r\n            r = r shl 1\n        }\n    }\n    \n    // Update value at index\n    fun update(idx: Int, value: Int) {\n        updateImpl(root, 0, N - 1, idx, value)\n    }\n    \n    // Increment counter at index\n    fun inc(idx: Int) {\n        update(idx, get(idx, idx) + 1)\n    }\n    \n    private fun updateImpl(node: Int, beg: Int, end: Int, idx: Int, value: Int) {\n        if (beg == end) {\n            data[node] = value\n            return\n        }\n        val mid = beg + (end - beg) / 2\n        if (idx <= mid) {\n            updateImpl(node * 2, beg, mid, idx, value)\n        } else {\n            updateImpl(node * 2 + 1, mid + 1, end, idx, value)\n        }\n        data[node] = data[node * 2] + data[node * 2 + 1]\n    }\n    \n    // Get sum in range [idxL, idxR]\n    fun get(idxL: Int, idxR: Int): Int {\n        return getImpl(1, 0, N - 1, idxL, idxR)\n    }\n    \n    private fun getImpl(node: Int, beg: Int, end: Int, idxL: Int, idxR: Int): Int {\n        if (idxL > end || idxR < beg) return 0\n        if (idxL <= beg && idxR >= end) return data[node]\n        val mid = beg + (end - beg) / 2\n        return getImpl(node * 2, beg, mid, idxL, idxR) +\n                getImpl(node * 2 + 1, mid + 1, end, idxL, idxR)\n    }\n}\n\nclass Solution {\n    fun resultArray(nums: IntArray): IntArray {\n        // Coordinate compression to map values to 0..k range\n        fun coordCompress(v: IntArray): IntArray {\n            val sorted = v.withIndex().sortedBy { it.value }\n            val cc = IntArray(v.size)\n            var j = -1\n            for (i in sorted.indices) {\n                if (i == 0 || sorted[i - 1].value < sorted[i].value) j++\n                cc[sorted[i].index] = j\n            }\n            return cc\n        }\n\n        val cc = coordCompress(nums)\n        val L = cc.maxOrNull()!! + 1\n        \n        // Initialize segment trees and result arrays\n        val st1 = SegT(L)\n        val st2 = SegT(L)\n        val a1 = mutableListOf<Int>()\n        val a2 = mutableListOf<Int>()\n        \n        // Process first two elements\n        var i = 0\n        a1.add(nums[i])\n        st1.inc(cc[i])\n        i++\n        \n        a2.add(nums[i])\n        st2.inc(cc[i])\n        i++\n        \n        // Process remaining elements\n        while (i < cc.size) {\n            // Count elements greater than current in both arrays\n            val c1 = st1.get(cc[i] + 1, L - 1)\n            val c2 = st2.get(cc[i] + 1, L - 1)\n            \n            // Decide which array to append to based on counts\n            when {\n                c1 > c2 -> {\n                    a1.add(nums[i])\n                    st1.inc(cc[i])\n                }\n                c1 < c2 || (c1 == c2 && a1.size > a2.size) -> {\n                    a2.add(nums[i])\n                    st2.inc(cc[i])\n                }\n                else -> {\n                    a1.add(nums[i])\n                    st1.inc(cc[i])\n                }\n            }\n            i++\n        }\n        \n        return (a1 + a2).toIntArray()\n    }\n}\n```\n\n```cpp []\nclass SegT {\npublic:\n    int N, root;\n    vector<int> data;\n\n    static int nxpow(int N) { for (int r = 1; true; r <<= 1) if (r >= N) return r; }\n\n    SegT(int N) : N(N), root(1), data(2 * nxpow(N)) {}\n\n    void update(int idx, int val) {\n        update_impl(root, 0, N - 1, idx, val);\n    }\n\n    void inc(int idx) {\n        update(idx, get(idx, idx) + 1);\n    }\n\n    void update_impl(int node, int beg, int end, int idx, int val) {\n        if (beg == end) {\n            data[node] = val;\n            return;\n        }\n        int mid = beg + (end - beg) / 2;\n        if (idx <= mid) {\n            update_impl(node * 2, beg, mid, idx, val);\n        } else {\n            update_impl(node * 2 + 1, mid + 1, end, idx, val);\n        }\n        data[node] = data[node * 2] + data[node * 2 + 1];\n    }\n\n    int get(int idx_l, int idx_r) {\n        return get_impl(1, 0, N - 1, idx_l, idx_r);\n    }\n\n    int get_impl(int node, int beg, int end, int idx_l, int idx_r) {\n        if (idx_l > end || idx_r < beg) return 0;\n        if (idx_l <= beg && idx_r >= end) return data[node];\n        int mid = beg + (end - beg) / 2;\n        return get_impl(node * 2, beg, mid, idx_l, idx_r) +\n                get_impl(node * 2 + 1, mid + 1, end, idx_l, idx_r);\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        auto argsort = [](const vector<int>& v) {\n            vector<int> as(v.size());\n            iota(as.begin(), as.end(), 0);\n            sort(as.begin(), as.end(), [&v](int a, int b) { return v[a] < v[b]; });\n            return as;\n        };\n        auto coord_compress = [&argsort](const vector<int>& v) {\n            vector<int> as = argsort(v);\n            vector<int> cc(as.size());\n            for (int i = 0, j = -1; i < as.size(); ++i)\n                cc[as[i]] = (i == 0 || v[as[i - 1]] < v[as[i]]) ? ++j : j;\n            return cc;\n        };\n\n        vector<int> cc = coord_compress(nums);\n\n        int L = *max_element(cc.begin(), cc.end()) + 1;\n        SegT st1(L);\n        SegT st2(L);\n        vector<int> a1;\n        vector<int> a2;\n        int i = 0;\n        a1.push_back(nums[i]);\n        st1.inc(cc[i]);\n        ++i;\n        a2.push_back(nums[i]);\n        st2.inc(cc[i]);\n        ++i;\n        for (; i < cc.size(); ++i) {\n            int c1 = st1.get(cc[i] + 1, L);\n            int c2 = st2.get(cc[i] + 1, L);\n            if (c1 > c2) {\n                a1.push_back(nums[i]);\n                st1.inc(cc[i]);\n            } else if (c1 < c2 || c1 == c2 && a1.size() > a2.size()) {\n                a2.push_back(nums[i]);\n                st2.inc(cc[i]);\n            } else {\n                a1.push_back(nums[i]);\n                st1.inc(cc[i]);\n            }\n        }\n\n        a1.insert(a1.end(), a2.begin(), a2.end());\n        return a1;\n    }\n};\n```\n\n```cpp\nvector<int> resultArray(vector<int>& nums) {\n    vector<int> as(nums.size());\n    iota(as.begin(), as.end(), 0);\n    sort(as.begin(), as.end(), [&nums](int a, int b) { return nums[a] < nums[b]; });\n    vector<int> cc(as.size());\n    for(int i = 0, j = 0; i < as.size(); ++i)\n        cc[as[i]] = i == 0 || nums[as[i - 1]] < nums[as[i]] ? ++j : j;\n\n    vector<int> f1(cc.size() + 1), f2(cc.size() + 1);\n    auto inc = [](vector<int>& fenw, int i) {\n        for (; i < fenw.size(); i += i & -i)\n            ++fenw[i];\n    };\n    auto get = [](vector<int>& fenw, int i) {\n        int sum = 0;\n        for (; i > 0; i -= i & -i)\n            sum += fenw[i];\n        return sum;\n    };\n\n    vector<int> a1, a2;\n    int i = 0;\n    a1.push_back(nums[i]);\n    inc(f1, cc[i]);\n    ++i;\n    a2.push_back(nums[i]);\n    inc(f2, cc[i]);\n    ++i;\n    for (; i < cc.size(); ++i) {\n        int gc1 = a1.size() - get(f1, cc[i]);\n        int gc2 = a2.size() - get(f2, cc[i]);\n        if (gc2 > gc1 || gc2 == gc1 && a2.size() < a1.size()) {\n            a2.push_back(nums[i]);\n            inc(f2, cc[i]);\n        } else {\n            a1.push_back(nums[i]);\n            inc(f1, cc[i]);\n        }\n    }\n\n    a1.insert(a1.end(), a2.begin(), a2.end());\n    return a1;\n}\n```
['C++', 'Kotlin']