BIT

struct bit {
    int n, MPOW;

    vector<int> tree;

    bit(int n) : n(n) {
        MPOW = 1;
        while ((1ll << (MPOW + 1)) <= n) MPOW++;
        tree = vector<int>(n, 0);
    }

    int sum(int i) {
        int res = 0;
        for (int ii = i; ii >= 0; ii = (ii & (ii + 1)) - 1) {
            res += tree[ii];
        }
        return res;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int i, int dif = 1) {
        for (int ii = i; ii < n; ii = ii | (ii + 1)) {
            tree[ii] += dif;
        }
    }

    int contains(int i) {
        return sum(i, i);
    }

    // how many before
    int order_by_key(int i) {
        return sum(0, i - 1);
    }

    // 1 based index
    int element_by_order(int ord) {
        int sum = 0;
        int ret = 0;
        for (int i = 1ll << MPOW; i && ret + (i - 1) < N; i >>= 1) {
            if (sum + tree[ret + (i - 1)] < ord) {
                sum += tree[ret + (i - 1)],
                    ret += i;
            }
        }
        return ret;
    }
};