**Segments( count of maximum no of overlaping segments that can be formed after rearranging segments )

Segments

A number of segments are lying on a line. Every segment is given with the coordinates of its endpoints. Segments are numbered from 1 to N (0 < N < 500). We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained in. In the sequence, every segment except the last is inside the next segment in the sequence.

Input

The first line contains one integer N. Next, there are N lines, with two integers on every line, which are the coordinates of the left and the right endpoints of the corresponding segment. These coordinates are integers in the interval [–10000, 10000]. We assume that, the given segments are numbered according to their place in the input.

Output

The first line must contain one integer, equal to the number of segments in the found sequence. The following line must contain the numbers of the segments in this sequence. These numbers must be outputted, in the order in which the segments' lengths increase, starting from the smallest. If there are more than one output sequences, write any of them.

Sample

input	output
4 -2 2 -1 1 -3 3 4 5	3 2 1 3

Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament 

Tags: dynamic programming  (

 hide tags for unsolved problems

 )

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

WE CAN EASILY CALCULATE ANSWER , MAIN THING IS FIXING START , MEANS LOWEST SEGMENT DECISSION , SINCE CONSTRAINTS ARE VERY LOW SOO TRY ONE BY ONE CONSIDER EACH SESMENT AS A START SEGMENT ,  NOW IN  AND MANY PART FOR REST OF SEGMENT AS A START WILL BE COMPUTED IN THE FIRST CALL,

NOW MAIN THING IS BACKTRACKING , RECURSIVE BACKTRACKING WILL BE THE EASIEST BACKTRACKING IN THIS PROBLEM ,

---------------------------------------------CODE--------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int dp[505];

vector<pair<int,int>  > v;

int n;

int  solve(int index)

 {

   if(index>=n) return 0;

   if(dp[index]!=-1) return dp[index];

   

   else

   {

     int xindex=v[index].first;

     int yindex=v[index].second;

     int ret=0;

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

     {

       if(v[i].first<xindex && v[i].second>yindex)

        {

         ret=max(ret,solve(i));

 }

     

   }

   dp[index]=ret+1;

   return dp[index];

  }

 }

 

 

 int cov=0;

   int ans=0;

 int print(int index)

  {

    if(index>=n) return 0;

    else if(cov==ans-1)

    {

     cout<<index+1<<endl;

     return 0;

   }

    else

     { 

int xindex=v[index].first;

     int yindex=v[index].second;

   

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

     {

       if(v[i].first<xindex && v[i].second>yindex && solve(index)==solve(i)+1)

        {

         cout<<index+1<<" ";

         cov++;

          print(i);

          break;

 }

     

   }

}

  }

 int main()

  {

    

     cin>>n;

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

      {

        int a,b;

         cin>>a>>b;

         v.push_back(make_pair(a,b));

 }

 for(int i=0;i<=n;i++) dp[i]=-1;

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

  {

     ans=max(ans,solve(i));

  }

     

       cout<<ans<<endl;

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

        {

          if(dp[i]==ans)

          {

           print(i);

           break;

 }

}

 

 return 0;

  }

***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;

  }

}