struct Node {
    ll key, pr;
    ll left = -1, right = -1, cnt;
    ll sz;
};

struct dd {
    //Djinchuriki Djubi
    vector <Node> nodes;
    ll nodesNumber = 0;
    ll kor = -1;
    ll makeNewNode(ll x) {
        nodes.push_back({ x, (int)rnd(), -1, -1, 1, 1 });
        return nodesNumber++;
    }
    ll getSZ(ll v) { return (v >= 0) ? nodes[v].sz : 0; }
    void recalculate(ll v) {
        if (v >= 0) {
            nodes[v].sz = getSZ(nodes[v].left) + getSZ(nodes[v].right) + nodes[v].cnt;
        }
    }
    bool exists(ll root, ll x) {
        ll v = root;
        while (v != -1) {
            Node& nd = nodes[v];
            if (nd.key == x)
                return true;
            else if (nd.key > x)
                v = nodes[v].left;
            else
                v = nodes[v].right;
        }
        return false;
    }
    pair <ll, ll> split(ll root, ll x) {
        if (root == -1)
            return { -1,-1 };
        if (x < nodes[root].key) {
            pair <ll, ll> p = split(nodes[root].left, x);
            nodes[root].left = p.second;
            recalculate(root);
            return { p.first, root };
        }
        else {
            pair <ll, ll> p = split(nodes[root].right, x);
            nodes[root].right = p.first;
            recalculate(root);
            return { root,p.second };
        }
    }
    ll merge(ll root1, ll root2) {
        if (root2 == -1) {
            return root1;
        }
        if (root1 == -1) {
            return root2;
        }
        if (nodes[root1].pr > nodes[root2].pr) {
            nodes[root1].right = merge(nodes[root1].right, root2);
            recalculate(root1);
            return root1;
        }
        else {
            nodes[root2].left = merge(root1, nodes[root2].left);
            recalculate(root2);
            return root2;
        }
    }
    ll insert(ll root, ll x) {
        if (exists(root, x)) {
            pair <ll, ll> p = split(root, x);
            pair <ll, ll> pp = split(p.first, x - 1);
            nodes[pp.second].cnt++;
            nodes[pp.second].sz++;
            return merge(merge(pp.first, pp.second), p.second);
        }
        else {
            ll newNode = makeNewNode(x);
            pair <ll, ll> p = split(root, x);
            return merge(p.first, merge(newNode, p.second));
        }
    }
    ll erase(ll root, ll x) {
        if (!exists(root, x)) {
            return root;
        }
        else {
            pair <ll, ll> p = split(root, x);
            pair <ll, ll> pp = split(p.first, x - 1);
            nodes[pp.second].cnt--;
            nodes[pp.second].sz--;
            if (nodes[pp.second].cnt == 0) {
                return merge(pp.first, p.second);
            }
            else {
                return merge(merge(pp.first, pp.second), p.second);
            }
        }
    }
    ll prev(ll root, ll x) {
        ll v = root, res = -inf, ans = 0;
        while (v != -1) {
            Node& nd = nodes[v];
            if (nd.key > x) {
                v = nd.left;
            }
            else {
                if (nd.key == x) {
                    ans += getSZ(nd.left);
                }
                else {
                    ans += getSZ(nd.left) + nd.cnt;
                }
                v = nd.right;
            }
        }
        return ans;
    }
};

struct fnw {
    vector <dd> fn;//Fenwick
    //I want to take vseros
    void build(ll n) {
        fn.resize(n + 4);
    }
    ll sump(ll r, ll x) {
        ll ans = 0;
        for (r; r > 0; r -= r & -r) {
            ans += fn[r].prev(fn[r].kor, x);
        }
        return ans;
    }
    ll sum(ll l, ll r, ll x) {
        // Кол-во элементов с l to r меньших x
        return sump(r, x) - sump(l - 1, x);
    }
    void add(ll r, ll val) {
        for (r; r < fn.size(); r += r & -r) {
            if (val > 0) {
                fn[r].kor = fn[r].insert(fn[r].kor, val);
            }
            else {
                fn[r].kor = fn[r].erase(fn[r].kor, -val);
            }
        }
    }
};