【8.08考试】　 隔膜

小ｓ是一个可爱的女孩子。

最近小ｓ迷上了一款明教ＣＯＧＳ的小游戏。这款游戏实在一个数轴上进行的，总共有ｎ快高度为１方块将从无限高处落下。第\(i\)块方块可以用二元组(\(l_i\),\(r_i\))表示。其含义是第\(i\)块方块长度为\(r_i\)-\(l_i\) 且左端点位于\(l_i\)，右端点位于\(r_i\)-1.第\(i\)个方块落下时如果数轴上的区间[\(l_i\),\(r_i\))内没有任何方块，那么这个方块就会落在最底层(即第一层);若数轴上的区间[\(l_i\),\(r_i\))内有方块的任何一个部分，那么这个方块就会落在这个区间内最高的方块的上一层。

现在小Ｓ可以任意安排这n个方块的下落顺序,她想知道这n个方块按安排的顺序下落后

1.最底层(第一层)　最多能有几个方块。

2.最低能有多少层。

注意，这两个问题是相互独立的。可是小S太可爱了,所以你要帮他解决这个问题。

Input

第一行一个正整数n,代表方块的个数.

接下来有n行，每行有两个数\(l_i\),\(r_i\) ,表示第\(i\)个方块的左端点和右端点+1。

Output

第一行两个数，分别表示第一个询问和第二个询问的答案。

Sample

Input

6

1 2

2 3

4 5

5 6

1 4

3 6

Output

4 2

Subtasks

对于30%的数据，n≤10,0≤l,r≤20,l\(<\)r;

对于另外20%的数据,n≤100,0≤l≤50,\(r_i\)=\(l_i\)+2;

对于100%的数据，n≤1e5,\(-2*10^8\)≤l≤r≤\(2*10^8\)

Solution

首先我们看第一问，一个基础的贪心，选不相交线段个数最多。按右端点排序，然后贪心选取线段，容易证明是正确的。

重点是第二问，我们可以发现，可以让当前区间每个节点+1，在判断最大值就行了，但l,r数据范围较大，离散一下就行了。

#include
    
     #include
     
      #include
      
       #include
       
        #define ll(x) (x*2)#define rr(x) (x*2+1)#define N 100000using namespace std;int sum[801000],lazy[800100],ans=1,t[810000],tot,hash[801001];struct Node{    int l,r;    bool operator< (const Node &c) const    {        if(r!=c.r)        return r
        
         =left&&r<=right)     {        sum[node]+=(r-l+1);        lazy[node]++;        return;    }    int mid=(l+r)/2;    pushdown(node,mid-l+1,r-mid);    if(left<=mid) gai(ll(node),l,mid,left,right);    if(right>mid) gai(rr(node),mid+1,r,left,right);    pushup(node);}void cha(int node,int l,int r){    if(l==r)    {        ans=max(ans,sum[node]);        return;    }    int mid=(l+r)/2;    pushdown(node,mid-l+1,r-mid);    cha(ll(node),l,mid);    cha(rr(node),mid+1,r);}int main(){    freopen("game.in","r",stdin);    freopen("game.out","w",stdout);    int n,x,y,last;    cin>>n;    for(int i=1;i<=n;i++)    {        scanf("%d%d",&x,&y);        a[i].l=x;a[i].r=y-1;        t[++tot]=x;hash[tot]=x;        t[++tot]=y-1;hash[tot]=y-1;    }    sort(a+1,a+1+n);    last=a[1].r;    for(int i=2;i<=n;i++)    {        if(a[i].l>last)        ans++,last=a[i].r;    }    cout<
         
          <<' '; ans=0; sort(t+1,t+1+tot); tot=unique(t+1,t+1+tot)-t-1; for(int i=1;i<=2*n;i++) hash[i]=lower_bound(t+1,t+1+tot,hash[i])-t; for(int i=1;i<=2*n;i+=2) gai(1,1,tot,hash[i],hash[i+1]); cha(1,1,tot); cout<