class Solution {

    //////////////////

    // Fenwick Tree //

    vector<long long> ft;

    void update(int i, long long x)

    {

        if (i == )

        {

            ft[] ++;

            return;

        }

        if ((i + ) > ft.size()) return;

        for (; i < ft.size(); i += (i & -i))

            ft[i] += x;

    }

    long long query(int i)

    {

        if (i == ) return ft[];

        i = min(i, int(ft.size() - ));

        long long s = ;

        for (; i > ; i -= (i & -i))

            s += ft[i];

        return s + ft[];

    }

    //////////////////

public:

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

        ft.assign(, );

        vector<int> ret;

        if(nums.size() < ) return {};

        //    handling neg

        auto r = minmax_element(nums.begin(), nums.end());

        int minv = *r.first;

        int maxv = *r.second;

        int d = ;

        vector<long long> ns;

        if (minv < )

        {

            d = -minv + ;

        }

        for (auto v : nums)

            ns.push_back(v + d);

        //

        for (int i = ns.size() - ; i >= ; i--)

        {

            int v = ns[i];

            int r = query(v - );

            update(v, );

            ret.push_back(r);

        }

        reverse(ret.begin(), ret.end());

        return ret;

    }

};