struct FenwTree{
    vi t;
    int n;
    FenwTree(int _n){
        n = _n;
        t.assign(n, 0);
    }
    void add(int i, int x){
        for(;i<n;i=(i|(i+1)))
            t[i] += x;
    }
    int get(int i){
        int res = 0;
        for(;i>=0;i=(i&(i+1))-1)
            res += t[i];
        return res;
    }
};