***D. Nested Segments

D. Nested Segments

You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.

Output

Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.

Examples

input

4
1 8
2 3
4 7
5 6

output

3
0
1
0

input

3
3 4
1 5
2 6

output

0
1
1

----------------------------------------editorial-----------------------------------------------------------------

this problem seems to be 2 dimensional ( means for counting  ans of ith segment we have to check all segment which lies in b/w its left and right  soo 2 dimenssion )     but we can can make it one dimensional by sorting , if  we sort the  pairs than  after sorting  ith   segment(in sorted position) ans for this segment must be from i+1 to n since segements form i-1 to 0 have  left  less than left of ith segment ..

so for ith segment we need to check from i+1 to n ( after sorting ) ,

but sill this is a o(n^2) approach we cant check for each segment  by iterating from i+1 th segment to n 

one another observation is that all segments which are in range from i+1 to n have right <  right of the ith segment will be the answer for the ith segment ., 

we  count this easily using range sum query ..

initilly hash all position of right of all segment and form a range sum seg tree so  over this array ..

now as soon as we calculate answer for the ith segment remove the right value of the ith segment from the hashed array and update the seg tree,

for   calculating ans of the ith segment ans= range sum in 1 to (right of ith segment -1 )  since all right  values in the hashed array   present   are eligible for  the ith segment  since ...

now there is another problem we  cannot has  segments right value easily since it is 10^9  soo we need to normalies ( compact ) it ....

-----------------------------------------------code---------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

vector<pair<pair<int,int>,int> > v,compact;

vector<int> all; 

int arr[10000000];

int ans[10000000];

int seg[10000000];

void build(int index,int l,int r)

 {

   if(l>r) return ;

   else if(l==r)

    {

     seg[index]=arr[l];

    

     return ;

   }

   build(2*index,l,(l+r)/2);

   build(2*index+1,((l+r)/2)+1,r); 

   // cout<<index<<" "<<" val "<<seg[2*index]+seg[2*index+1]<<endl;;;

   seg[index]=seg[2*index]+seg[2*index+1];

 } 

int qry(int index,int start,int end,int qs,int qe )

  {

         if(start>end || end<qs || start>qe)

           {

            return 0;

            }

        if(start>=qs && end<=qe)

          {

            return  seg[index];

          }

        int q1=qry(2*index,start,(start+end)/2,qs,qe);

         int q2=qry(2*index+1,((start+end)/2)+1,end,qs,qe);

         return q1+q2;

  }

  

  void update(int index,int start,int end,int ups,int upe)

   {

   if(start>end || start>upe || end<ups) return ;

   if(start>=ups && end<=upe)

    {

       seg[index]-=1;

       return ;

}

     update(2*index,start,(start+end)/2,ups,upe);

     update(2*index+1,((start+end)/2)+1,end,ups,upe);

     seg[index]=seg[2*index]+seg[2*index+1];

   }

int main()

{

 int n;

  cin>>n;

  for(int i=0;i<n;i++)

   {

    int l,r;

     cin>>l>>r;

     v.push_back({{l,r},i});

     all.push_back(l);

     all.push_back(r);

     

   }

   sort(all.begin(),all.end());

   for(int i=0;i<n;i++)

    {

       int idx=v[i].second;

       int l=v[i].first.first;

       int  r=v[i].first.second;

       //cout<<" inni "<<l<<" "<<r<<" "<<idx<<endl;

       // cout<<*lower_bound(all.begin(),all.end(),l)<<"m "<<*lower_bound(all.begin(),all.end(),r)<<endl;

        int lc=lower_bound(all.begin(),all.end(),l)-all.begin();

        int rc=lower_bound(all.begin(),all.end(),r)-all.begin();

       // cout<<lc<<" "<<rc<<" "<<idx<<endl;

        arr[rc+1]++;

        

       compact.push_back({{lc+1,rc+1},idx});

}

build(1,1,2*n);

sort(compact.begin(),compact.end());

for(int i=0;i<n;i++)

 {

  int idx=compact[i].second;

  int l=compact[i].first.first;

  int r=compact[i].first.second;

 //  cout<<" find sum till "<<r<<endl;

   int val=qry(1,1,2*n,1,r-1);

  //  cout<<" val "<<val<<endl;

   ans[idx]=val;

   update(1,1,2*n,r,r);

 }

 for(int i=0;i<n;i++)

  {

     cout<<ans[i]<<" "<<endl;

  }

}