const pair<int, int> NEU = {0, -INF};

struct Node {
    Node *L, *R;
    pair<int, int> val = NEU;
} *root = new Node();

pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.first >= b.first)
        return {a.first, a.second};
    return {b.first, b.second};
}

void update(Node *cur, int pos, int x, int tl = 0, int tr = INF) {
    if (!cur)
        return;
    if (tl == tr - 1) {
        cur->val = {x, pos};
        return;
    }

    if (!cur->L)
        cur->L = new Node();
    if (!cur->R)
        cur->R = new Node();

    int mid = (tl + tr) / 2;

    if (pos < mid)
        update(cur->L, pos, x, tl, mid);
    else
        update(cur->R, pos, x, mid, tr);
    cur->val = merge(cur->L->val, cur->R->val);
}

pair<int, int> get(Node *cur, int l, int r, int tl = 0, int tr = INF) {
    if (!cur)
        return NEU;
    if (l >= tr || tl >= r)
        return NEU;
    if (l <= tl && tr <= r)
        return cur->val;
    int mid = (tl + tr) / 2;

    return merge(get(cur->L, l, r, tl, mid), get(cur->R, l, r, mid, tr));
}