struct Node {
    int v, size, cnt;
    Node *p, *ch[2];
    bool d()        {
        return p->ch[1] == this;
    }
    int cmp(int vv) {
        return v==vv?-1:v<vv;
    }
    void setc(Node *c, bool d) {
        ch[d] = c, c->p = this;
    }
    void pushup() {
        size = cnt + ch[0]->size + ch[1]->size;
    }
}*null, *root, *now, pool[maxn];
void init()
{
    now = pool;
    null = new Node();
    null->size = 0;
    root = null;
}
inline Node* new_node(int v)
{
    now->v = v, now->ch[0] = now->ch[1] = null, now->size = now->cnt = 1;
    return now++;
}
void rot(Node *t)
{
    Node *p = t->p;
    bool d = t->d();
    p->p->setc(t, t->p->d());
    p->setc(t->ch[d^1], d);
    t->setc(p, d^1);
    p->pushup();
    if (p == root)      root = t;
}
bool FLAG;
void splay(Node *t, Node *f)
{
    if (t == null)      return;
    for (; t->p != f;) {
        if (t->p->p == f) {
            rot(t);
        } else {
            t->d() == t->p->d() ? (rot(t->p), rot(t)) : (rot(t), rot(t));
        }
    }
    t->pushup();
}
void insert(int v, Node *&root)
{
    if (root == null) {
        Node *p = new_node(v);
        root = p, p->p = null;
        return;
    }
    Node *p, *q;
    int d;
    for (p = root; p != null;) {
        d = p->cmp(v);
        if (d == -1) {
            ++p->cnt, ++p->size;
            splay(p, null);
            return;
        }
        q = p;
        p = p->ch[d];
    }
    p = new_node(v);
    q->setc(p, d);
    splay(p, null);
}
void erase(Node *t)
{
    if (t == null)      return;
    if (t->p == null) {
        root = null;
        return;
    }
    Node *p = t->p;
    p->ch[t->d()] = null, p->pushup();
}
 
// 在以root为根的树内 找第k小节点  注意k是在树内的次序   如果设置了A[0]=A[n+1]=inf的话 原来序列内的k需要+1  维护序列版select
Node *select(Node *root, int k)
{
    Node *p=root;
    for (; p!=null;) {
        if (k == p->ch[0]->size+1)
            return p;
        if (k <= p->ch[0]->size)
            p = p->ch[0];
        else
            k -= p->ch[0]->size+1, p = p->ch[1];
    }
    return p;
}
 
// 设置了A[0]=A[n+1]=inf 然后提取区间[l,r] 维护序列
Node *getSeg(int L, int R)
{
    Node *p = select(root, L-1+1);
    splay(p, null);
    Node *q = select(root, R+1+1);
    splay(q, p);
    return root->ch[1]->ch[0];
}
//以P[L]..P[R]建立树 返回根 维护序列
Node *build(int L, int R, int P[])
{
    if (L > R)          return null;
    int m = (L+R)>>1;
    Node *p = new_node(P[m]);
    if (L < R) {
        p->setc(build(L, m-1, P), 0);
        p->setc(build(m+1, R, P), 1);
        p->pushup();
    }
    return p;
} 
Node* select(Node *root, int k)
{
    if (root == null)
        return null;
    Node *p;
    for (p = root; p != null;) {
        if (p->ch[0]->size >= k)
            p = p->ch[0];
        else if (p->ch[0]->size + p->cnt < k) {
            k -= p->ch[0]->size+ p->cnt;
            p = p->ch[1];
        } else
            return p;
    }
    return p;
}
// 在以root为根的子树内找到小于vv的最大节点
Node *less_bound(int vv, Node *root)
{
    Node *res = null;
    for (Node*p = root; p != null;) {
        if (p->v < vv) {
            res = p;
            p = p->ch[1];
        } else
            p = p->ch[0];
    }
    return res;
}
typedef Node *node; 


 
// 区间更新版本 
 
struct Node {
    LL sum, add, v;
    Node *ch[2], *p;
    int size;
    bool d()    {
        return p->ch[1]==this;
    }
    void setc(Node *c, bool d) {
        ch[d]=c, c->p=this;
    }
    void pushup() {
        sum = v + ch[0]->sum + ch[1]->sum;
        size = 1 + ch[0]->size + ch[1]->size;
    }
    void pushdown() {
        if (add) {
            rep(i, 2)
            ch[i]->sum += (LL)ch[i]->size*add, ch[i]->v += add, ch[i]->add += add;
            add = 0;
        }
    }
    void markAdd(int y) {
        add += y, v += y;
        sum += (LL)size*y;
    }
}*root, *null, *nowp, pool[maxn];
void init()
{
    null = new Node();
    null->sum=0, null->add=0, null->size=0, null->ch[0]=null->ch[1]=null->p=null;
    root = null, nowp = pool;
}
Node *newNode(int vv)
{
    nowp->v = vv, nowp->sum = vv, nowp->add = 0, nowp->size = 1;
    nowp->ch[0]=nowp->ch[1]=nowp->p=null;
    return nowp++;
}
Node *build(int L, int R, int A[])
{
    if (L>R)        return null;
    int m = L+((R-L)>>1);
    Node *p = newNode(A[m]);
    if (L<R) {
        p->setc(build(L, m-1, A), 0);
        p->setc(build(m+1, R, A), 1);
        p->pushup();
    }
    return p;
}
Node *select(Node *root, int k)
{
    for (Node *p=root; p!=null;) {
        p->pushdown();
        if (k == p->ch[0]->size+1)
            return p;
        if (k <= p->ch[0]->size)
            p = p->ch[0];
        else
            k -=p->ch[0]->size+1, p = p->ch[1];
    }
    return null;
}
void rot(Node *t)
{
    Node *p = t->p;
    p->pushdown(), t->pushdown();
    bool d = t->d();
    p->p->setc(t, p->d());
    p->setc(t->ch[d^1], d);
    t->setc(p, d^1);
    p->pushup();
    if (p == root)
        root = t;
}
void splay(Node *t, Node *f)
{
    for (t->pushdown(); t->p!=f;) {
        if (t->p->p == f)
            rot(t);
        else
            (t->d() == t->p->d()) ? (rot(t->p), rot(t)) : (rot(t), rot(t));
    }
    t->pushup();
}
Node *getSeg(int L, int R)
{
    Node *p = select(root, L-1+1);
    splay(p, null);
    Node *q = select(root, R+1+1);
    splay(q, root);
    return root->ch[1]->ch[0];
} 
 
// merge two splay tree. p, q should be root. return the root
Node *merge(Node *p, Node *q)
{
    p->f = q->f = null;
    if (p == null) return q;
    if (q == null) return p;
    q = select(q, 1);
    q->Splay();
    q->set(0, p);
    q->update();
    return q;
}