struct Tree {
    int val;
    Tree *left;
    Tree *right;
    int smaller_left;
    int dup;

    Tree( int x) : val(x), left(nullptr), right(nullptr),  dup(1), smaller_left(0) {}
};



class Solution {
public:
    Tree* insert_order (Tree *root, int val, int count, int &res)
    {
        if (root == nullptr)
        {
            Tree* n_node = new Tree(val);
            res = count; // extra

            return n_node;
        }

        if (val > root -> val)
        {
            int newCount =  count + root -> smaller_left + root->dup; // extra
            root -> right = insert_order (root -> right, val,  newCount ,res);
        }
        else if (val < root -> val)
        {

            root -> smaller_left++; // extra
            root -> left = insert_order (root -> left , val,count ,res);
        }
        else
        {
            root -> dup ++; // extra
            res = count + root->smaller_left;

        }
        return root;
    }

    vector<int> countSmaller(vector<int>& nums) {

        int sz = nums.size();

        vector <int> res (sz,0);

        if (sz == 0) return {};

        int cur_res = 0;
        Tree *root = insert_order (nullptr, nums[sz - 1],0, cur_res);
        res[sz - 1] = cur_res;
        for (int i = sz - 2 ; i >= 0; i--)
        {
            cur_res = 0;
            Tree* n_node = insert_order (root, nums[i],0,cur_res);
            res[i] = cur_res;
        }
        return res;
    }
};


class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int sz = nums.size();
        multiset <int> my_set;
        vector <int> res (sz ,0);
        for (int i = sz - 1; i >= 0 ; i --)
        {
            int x = nums[i];
            my_set.insert (x);

            auto it = my_set.lower_bound (x);

            res[i] = distance (my_set.begin(), it);
        }
        return res;
    }
};

/*
time = O(n*logn*n)

*/