struct Node
{
    bool isrev;
    int key;
    long long prior;
    int sz;
    int mn;
    Node *l = nullptr, *r = nullptr;
    Node(int _key)
    {
        isrev = 0, sz = 1, mn = key = _key, prior = abs((long long)gen64());
    }
};
void push(Node* v)
{
    if (!v)
        return;
    if (v->isrev)
    {
        swap(v->l, v->r);
        if (v->l)
            v->l->isrev ^= 1;
        if (v->r)
            v->r->isrev ^= 1;
    }
    v->isrev = 0;
}
int sum(Node* v)
{
    return v ? v->sz : 0;
}
int min(Node* v)
{
    push(v);
    return v ? v->mn : INT_MAX;
}
void upd(Node* v)
{
    if (!v)
        return;
    v->sz = sum(v->l) + sum(v->r) + 1;
    v->mn = min(v->key, min(min(v->l), min(v->r)));
}

Node* merge(Node* l, Node* r)
{
    push(l);
    push(r);
    if (!l)
        return r;
    if (!r)
        return l;
    if (l->prior > r->prior)
    {
        l->r = merge(l->r, r);
        upd(l);
        return l;
    }
    else
    {
        r->l = merge(l, r->l);
        upd(r);
        return r;
    }
}

pair<Node*, Node*> split(Node* p, int x)
{
    push(p);
    if (!p)
        return{ 0, 0 };
    if (sum(p->l) + 1 <= x)
    {
        Node *L, *R;
        tie(L, R) = split(p->r, x - 1 - sum(p->l));
        p->r = L;
        upd(p);
        return{ p, R };
    }
    else
    {
        Node *L, *R;
        tie(L, R) = split(p->l, x);
        p->l = R;
        upd(p);
        return{ L, p };
    }
}

int goleft(Node* x)
{
    if (!x)
        return INT_MIN;
    if (!x->l)
        return x->key;
    return goleft(x->l);
}

int next(Node* rt, int x)
{
    Node *L, *R;
    tie(L, R) = split(rt, x + 1);
    int ans = goleft(R);
    merge(L, R);
    return ans;
}

int goright(Node* x)
{
    if (!x)
        return INT_MIN;
    if (!x->r)
        return x->key;
    return goright(x->r);
}

int prev(Node* rt, int x)
{
    Node *L, *R;
    tie(L, R) = split(rt, x);
    int ans = goright(L);
    merge(L, R);
    return ans;
}

int find2(Node* rt, int x)
{
    return next(rt, x - 1);
}

Node* insert(Node* rt, int x, int idx)
{
    Node *L, *R;
    tie(L, R) = split(rt, idx);
    Node* T = new Node(x);
    return merge(L, merge(T, R));
}

Node* remove(Node* rt, int x)
{
    Node *T, *R, *L, *M;
    tie(T, R) = split(rt, x + 1);
    tie(L, M) = split(T, x);
    return merge(L, R);
}

Node* move2front(Node* rt, int x, int y)
{
    // L M R --> M L R
    Node *T, *R, *L, *M;
    tie(T, R) = split(rt, y);
    tie(L, M) = split(T, x);
    return merge(M, merge(L, R));
}

Node* reverse(Node* rt, int x, int y)
{
    // L M R --> L M! R
    Node *T, *R, *L, *M;
    tie(T, R) = split(rt, y);
    tie(L, M) = split(T, x);
    push(M);
    upd(M);
    M->isrev ^= 1;
    return merge(merge(L, M), R);
}

Node* mov(Node* rt, int x, int y)
{
    Node *L, *M1, *M2, *R;
    tie(L, R) = split(rt, y);
    tie(L, M2) = split(L, y - 1);
    tie(L, M1) = split(L, x);
    return rt = merge(merge(L, M2), merge(M1, R));
}

long long mv(Node*& rt, int x, int y)
{
    // L M R --> L M! R
    Node *T, *R, *L, *M;
    tie(T, R) = split(rt, y);
    tie(L, M) = split(T, x);
    push(M);
    upd(M);
    int ans = min(M);
    rt = merge(merge(L, M), R);
    return ans;
}

void prn2(Node* rt)
{
    if (!rt)
        return;
    push(rt);
    upd(rt);
    prn2(rt->l);
    cout << " " << rt->key;
    prn2(rt->r);
}

void prn3(Node* rt, vector<int> &v)
{
    if (!rt)
        return;
    push(rt);
    upd(rt);
    prn3(rt->l, v);
    v.push_back(rt->key);
    prn3(rt->r, v);
}