✅ Reverse BIT with map | Clean Solution
IntuitionBinaryIndexedTree (BIT) is typically used for prefix sum formats where we aggregate results from 0 to target index. As we want no. of elements greater
# Intuition
BinaryIndexedTree (BIT) is typically used for prefix sum formats where we aggregate results from 0 to target index. As we want no. of elements greater than the target, we can flip the BIT to use it like suffix tree. Furthermore, we use map based lookup to optimize the space complexity

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```java []
class Solution {
    public int[] resultArray(int[] nums) {
        assert nums.length >= 3 : "nums size should be >= 3";
        int maxVal = Arrays.stream(nums).max().getAsInt();
        final List<Integer> arr1 = new ArrayList<>();
        final var bit1 = new BinaryIndexedTree(maxVal+1); // +1 to accomodate maxVal
        final List<Integer> arr2 = new ArrayList<>();
        final var bit2 = new BinaryIndexedTree(maxVal+1);
        arr1.add(nums[0]); bit1.add(nums[0], 1);
        arr2.add(nums[1]); bit2.add(nums[1], 1);
        for (int i=2; i<nums.length; i++) {
            int num = nums[i];
            int fg = bit1.sum(num+1); // +1 for strictly greater
            int sg = bit2.sum(num+1);
            int fs = arr1.size(), ss=arr2.size();
            if (fg>sg || (fg==sg && fs<=ss)) {
                arr1.add(num);
                bit1.add(num, 1);
            } else {
                arr2.add(num);
                bit2.add(num, 1);
            }
        }
        int[] res = new int[nums.length];
        int resi=0;
        for (int num: arr1) res[resi++] = num;
        for (int num: arr2) res[resi++] = num;
        return res;
    }
}

class BinaryIndexedTree {
    Map<Integer, Integer> bit;
    int n;
    BinaryIndexedTree(int size) {
        this.n = size;
        bit = new HashMap<>();
    }

    void add(int index, int val) {
        int i = index+1;
        while (i > 0) {
            bit.compute(i, (k,v) -> v==null ? 1 : v+1);
            i -= (i & -i);
        }
    }

    int sum(int index) {
        int i = index+1;
        int ans = 0;
        while (i <= n) {
            ans += bit.getOrDefault(i, 0);
            i += (i & -i);
        }
        return ans;
    }
}
```
['Binary Indexed Tree', 'Java']