描述

小Ho在玩一款类似俄罗斯方块的游戏。与原版俄罗斯方块不同的是，落下方块都是长度不一的横向长条，并且不能移动也不能变成竖直方向。

XXXXXX  <- 长度为6的横向长条。

第i个长条的最左端的格子坐标是Li，最右端的格子坐标是Ri；长条从很高的位置下落，中途遇到地面或者受到之前长条支撑，就会停在当前高度。

你能计算出每个长条最后停留的高度是多少吗？ 直接停在地面上的长条高度视为1。

例如5个长条依次下落的位置是[10, 15], [7, 12], [12, 19], [1, 4], [1, 7]，则每个长条最终停留的位置如下图所示：

5555555    33333333

      222222

4444     111111

输入

第一行包含一个整数N。

以下N行每行包含两个整数Li, Ri。

对于30%的数据，1 ≤ N ≤ 1000, 1 ≤ Li ≤ Ri ≤ 1000

对于100%的数据， 1 ≤ N ≤ 100000, 1 ≤ Li ≤ Ri ≤ 100000

输出

输出N行，每行包含一個整数，代表第i个长条停留的高度。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=;

int N,L,R,x,y,z;

struct Segment_Tree{

    int maxx;

    int tag;

}T[maxn<<];

void upd(int L,int R,int root){

    if(x>R||y<L)return;

    if(x<=L&&y>=R){ T[root].maxx=z; T[root].tag=z;return;}

    int mid=(L+R)>>;

    if(T[root].tag) T[root<<].maxx=T[root<<|].maxx=T[root<<].tag=T[root<<|].tag=T[root].tag,T[root].tag=;

    upd(L,mid,root<<);

    upd(mid+,R,root<<|);

    T[root].maxx=max(T[root<<].maxx,T[root<<|].maxx);

}

int query(int L,int R,int root){

    if(x>R||y<L) return ;

    if(x<=L&&y>=R) return T[root].maxx;

    int mid=(L+R)>>;

    if(T[root].tag)  T[root<<].maxx=T[root<<|].maxx=T[root<<].tag=T[root<<|].tag=T[root].tag,T[root].tag=;

    return max(query(L,mid,root<<),query(mid+,R,root<<|));

}

int main(){

    scanf("%d",&N);

    for(int i=;i<=N;i++){

        scanf("%d%d",&x,&y);

        int temp=query(,,);

        z=temp+;

        printf("%d\n",z);

        upd(,,);

    }

    return ;

}