Segment Tree + Compressed Indices
Intuition\nThe key is to realize greater count in log(n), which can be done using segment tree. However, you will get integer overflow while initializing the se
# Intuition\nThe key is to realize greater count in log(n), which can be done using segment tree. However, you will get integer overflow while initializing the seg tree without compressing indices because  1 <= nums[i] < 10^9.\n\n\n# Code\n```\nclass Solution {\n    class Segment_tree {\n    int n;\n    int[] tree;\n\n    public Segment_tree(int size) {\n        this.n = size;\n        tree = new int[4 * n]; \n    }\n\n    void update(int index, int value, int node, int left, int right) {\n        if (left == right) {\n            tree[node] = tree[node] + 1;\n            return;\n        }\n        int mid = (left + right) / 2;\n        if (index <= mid) {\n            update(index, value, 2 * node, left, mid);\n        } else {\n            update(index, value, 2 * node + 1, mid + 1, right);\n        }\n        tree[node] = tree[2 * node] + tree[2 * node + 1]; \n    }\n\n    int query(int qleft, int qright, int node, int left, int right) {\n        if (qleft > right || qright < left) return 0; \n\n        if (qleft <= left && qright >= right) {\n            return tree[node]; \n        }\n        int mid = (left + right)/2;\n        int left_count = query(qleft, qright, 2 * node, left, mid);\n        int right_count = query(qleft, qright, 2 * node + 1, mid + 1, right);\n        return left_count + right_count; \n    }\n    }\n\n    public int[] resultArray(int[] nums) {\n        TreeSet<Integer> set = new TreeSet<>();\n        for(int i = 0; i < nums.length; i++) set.add(nums[i]);\n\n        int n = nums.length, idx = 1, max = set.size();\n        HashMap<Integer, Integer> map = new HashMap<>();\n\n        for(Integer num : set) map.put(num, idx++);\n        \n        int[] arr1 = new int[n], arr2 = new int[n];\n\n        Segment_tree tree01 = new Segment_tree(max), tree02 = new Segment_tree(max);\n\n        arr1[0] = nums[0];\n        tree01.update(map.get(nums[0]), 1, 1, 1, max);\n        arr2[0] = nums[1];\n        tree02.update(map.get(nums[1]), 1, 1, 1, max);\n        \n        int idx1 = 0, idx2 = 0;\n        \n        for(int i = 2; i < nums.length; i++){\n            int count01 = tree01.query(map.get(nums[i]) + 1, max, 1, 1, max);\n            int count02 = tree02.query(map.get(nums[i]) + 1, max, 1, 1, max);\n\n            boolean arr01added = count01 == count02 && (idx1 == idx2 || idx1 < idx2);\n            arr01added = arr01added || (count01 > count02);\n\n            if(arr01added){\n                arr1[++idx1] = nums[i];\n                tree01.update(map.get(nums[i]), 1, 1, 1, max);\n            }else{\n                arr2[++idx2] = nums[i];\n                tree02.update(map.get(nums[i]), 1, 1, 1, max);\n            }\n\n        }\n     \n        int[] ans = new int[n];\n        for(int i = idx1; i >= 0; i--) ans[i] = arr1[i];\n        for(int i = nums.length - 1; i >= idx1 + 1; i--) ans[i] = arr2[i - (idx1 + 1)];\n\n        return ans;\n    }\n}\n```
['Segment Tree', 'Java']