#include<cstring>
#include<cstdlib>
//#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
pair< int ,int > v;
int ansv;
int ansi;
int sz;
Node * l;
Node * r;
Node * p;
} ;
Node * root;
void UpdateSize( Node * P)
{
P- > sz= 1 ;
if ( P- > l) P- > sz+ = P- > l- > sz;
if ( P- > r) P- > sz+ = P- > r- > sz;
}
void RightRotate( Node * P)
{
Node * T= P- > l;
Node * B= T- > r;
Node * D= P- > p;
if ( D)
{
if ( D- > l== P) D- > l= T;
else D- > r= T;
}
if ( B)
B- > p= P;
P- > p= T;
P- > l= B;
UpdateSize( P) ;
T- > r= P;
T- > p= D;
UpdateSize( T) ;
}
void LeftRotate( Node * P)
{
Node * T= P- > r;
Node * B= T- > l;
Node * D= P- > p;
if ( D)
{
if ( D- > l== P) D- > l= T;
else D- > r= T;
}
if ( B)
B- > p= P;
P- > p= T;
P- > r= B;
UpdateSize( P) ;
T- > l= P;
T- > p= D;
UpdateSize( T) ;
}
void Splay( Node * P)
{
while ( P- > p)
{
Node* PP= P- > p;
Node* PPP= PP- > p;
if ( ! PPP)
{
if ( PP- > l== P) RightRotate( PP) ;
else LeftRotate( PP) ;
break ;
}
if ( PPP- > l== PP)
{
if ( PP- > l== P)
{
RightRotate( PPP) ;
RightRotate( PP) ;
}
else
{
LeftRotate( PP) ;
RightRotate( PPP) ;
}
}
else
{
if ( PP- > l== P)
{
RightRotate( PP) ;
LeftRotate( PPP) ;
}
else
{
LeftRotate( PPP) ;
LeftRotate( PP) ;
}
}
}
root= P;
}
void Insert( pair< int , int > v,int ansv,int ansi)
{
Node * T= root;
if ( ! T)
{
root= ( Node* ) malloc ( sizeof ( Node) ) ;
root- > l= NULL ;
root- > r= NULL ;
root- > p= NULL ;
root- > v= v;
root- > sz= 1 ;
root- > ansv= ansv;
root- > ansi= ansi;
return ;
}
while ( T)
{
if ( v < ( T- > v) )
{
if ( T- > l)
{
T= T- > l;
continue ;
}
else
{
T- > l= ( Node * ) malloc ( sizeof ( Node) ) ;
T- > l- > l= NULL ;
T- > l- > r= NULL ;
T- > l- > p= T;
T- > l- > v= v;
T- > l- > ansv= ansv;
T- > l- > ansi= ansi;
T- > l- > sz= 1 ;
T= T- > l;
break ;
}
}
else
{
if ( T- > r)
{
T= T- > r;
continue ;
}
else
{
T- > r= ( Node * ) malloc ( sizeof ( Node) ) ;
T- > r- > l= NULL ;
T- > r- > r= NULL ;
T- > r- > p= T;
T- > r- > v= v;
T- > r- > ansv= ansv;
T- > r- > ansi= ansi;
T- > r- > sz= 1 ;
T= T- > r;
break ;
}
}
}
Node* tosplay= T;
while ( T)
{
UpdateSize( T) ;
T= T- > p;
}
Splay( tosplay) ;
}
Node* Find( pair< int ,int > v)
{
Node * T= root;
while ( T)
{
if ( v== ( T- > v) )
{
Splay( T) ;
return T;
}
if ( v< ( T- > v) )
{
if ( T- > l)
{
T= T- > l;
}
else
{
Splay( T) ;
return NULL ;
}
}
else
{
if ( T- > r)
{
T= T- > r;
}
else
{
Splay( T) ;
return NULL ;
}
}
}
return NULL ;
}
void Erase( Node * T)
{
Splay( T) ;
if ( T- > l)
{
root= T- > l;
Node * x= root;
while ( x- > r) x= x- > r;
x- > r= T- > r;
if ( T- > r) T- > r- > p= x;
while ( x- > p)
{
UpdateSize( x) ;
x= x- > p;
}
}
else
root= T- > r;
free ( T) ;
if ( root) root- > p= NULL ;
}
Node* findKth( Node * T,int K)
{
int sz= 0 ;
if ( T- > l) sz= T- > l- > sz;
if ( sz== K) return T;
if ( sz> K)
return findKth( T- > l,K) ;
else
return findKth( T- > r,K- sz- 1 ) ;
}
Node* findKth( int K)
{
Node* Kth= findKth( root,K) ;
Splay( Kth) ;
return Kth;
}
int R;
const int MAXN= 131072 ;
int idx[ MAXN* 2 ] ;
int getmax( int l,int r)
{
l+ = MAXN;
r+ = MAXN;
int ans= 0 ;
while ( l<= r)
{
if ( l% 2 == 1 )
ans= max( ans,idx[ l++ ] ) ;
if ( r% 2 == 0 )
ans= max( ans,idx[ r-- ] ) ;
l/ = 2 ;
r/ = 2 ;
}
return ans;
}
void Query( int A,int B) //from Ath Node to Bth Node (0-based)
{
int findcount= B- A+ 1 ;
Node * Ath= findKth( A) ;
Node * Bth= findKth( B) ;
//printf("%d %d %d %d\n",A,B,(Ath->v).first,(Bth->v).first);
int ansv= - 1 ;
int ansi= - 1 ;
pair< int ,int > v= make_pair( ( Ath- > v) .first ,( Bth- > v) .second ) ;
//printf("%d\n",root->sz);
for ( int i= 0 ; i< findcount; i++ )
{
// printf("%d %d\n",root->sz,A);
Node * Ath= findKth( A) ;
if ( ansv < ( Ath- > ansv) )
{
ansv= Ath- > ansv;
ansi= Ath- > ansi;
}
//printf("%d\n",root->sz);
Erase( Ath) ;
}
//puts("ok");
int ans= getmax( v.first ,v.second - 1 ) ;
if ( ans< R) ansv++ ;
Insert( v,ansv,ansi) ;
}
int GetBestPosition( int N, int C, int R, int * K, int * S, int * E)
{
:: R = R;
for ( int i= 0 ; i< N; i++ )
Insert( make_pair( i,i) ,0 ,i) ;
for ( int i= 0 ; i< N- 1 ; i++ )
idx[ MAXN+ i] = K[ i] ;
for ( int i= MAXN- 1 ; i>= 1 ; i-- )
idx[ i] = max( idx[ 2 * i] ,idx[ 2 * i+ 1 ] ) ;
for ( int i= 0 ; i< C; i++ )
Query( S[ i] ,E[ i] ) ;
return root- > ansi;
}
I2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8Y3N0ZGxpYj4KLy8jaW5jbHVkZTxjc3RkaW8+CiNpbmNsdWRlPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc3RydWN0IE5vZGUKewogICAgcGFpcjxpbnQsaW50PiB2OwogICAgaW50IGFuc3Y7CiAgICBpbnQgYW5zaTsKICAgIGludCBzejsKICAgIE5vZGUgKmw7CiAgICBOb2RlICpyOwogICAgTm9kZSAqcDsKfTsKTm9kZSAqcm9vdDsKdm9pZCBVcGRhdGVTaXplKE5vZGUgKlApCnsKICAgIFAtPnN6PTE7CiAgICBpZihQLT5sKSBQLT5zeis9UC0+bC0+c3o7CiAgICBpZihQLT5yKSBQLT5zeis9UC0+ci0+c3o7CiAgICAgCn0Kdm9pZCBSaWdodFJvdGF0ZShOb2RlICpQKQp7CiAgICBOb2RlICpUPVAtPmw7CiAgICBOb2RlICpCPVQtPnI7CiAgICBOb2RlICpEPVAtPnA7CiAgICBpZihEKQogICAgewogICAgICAgIGlmKEQtPmw9PVApIEQtPmw9VDsKICAgICAgICBlbHNlIEQtPnI9VDsKICAgIH0KICAgIGlmKEIpCiAgICAgICAgQi0+cD1QOwogICAgIAogICAgUC0+cD1UOwogICAgUC0+bD1COwogICAgVXBkYXRlU2l6ZShQKTsKICAgICAKICAgIFQtPnI9UDsKICAgIFQtPnA9RDsKICAgIFVwZGF0ZVNpemUoVCk7Cn0Kdm9pZCBMZWZ0Um90YXRlKE5vZGUgKlApCnsKICAgIE5vZGUgKlQ9UC0+cjsKICAgIE5vZGUgKkI9VC0+bDsKICAgIE5vZGUgKkQ9UC0+cDsKICAgIGlmKEQpCiAgICB7CiAgICAgICAgaWYoRC0+bD09UCkgRC0+bD1UOwogICAgICAgIGVsc2UgRC0+cj1UOwogICAgfQogICAgaWYoQikKICAgICAgICBCLT5wPVA7CiAgICAgCiAgICBQLT5wPVQ7CiAgICBQLT5yPUI7CiAgICBVcGRhdGVTaXplKFApOwogICAgIAogICAgVC0+bD1QOwogICAgVC0+cD1EOwogICAgVXBkYXRlU2l6ZShUKTsKfQp2b2lkIFNwbGF5KE5vZGUgKlApCnsKICAgIHdoaWxlKFAtPnApCiAgICB7CiAgICAgICAgTm9kZSogUFA9UC0+cDsKICAgICAgICBOb2RlKiBQUFA9UFAtPnA7CiAgICAgICAgaWYoIVBQUCkKICAgICAgICB7CiAgICAgICAgICAgIGlmKFBQLT5sPT1QKSBSaWdodFJvdGF0ZShQUCk7CiAgICAgICAgICAgIGVsc2UgTGVmdFJvdGF0ZShQUCk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpZihQUFAtPmw9PVBQKQogICAgICAgIHsKICAgICAgICAgICAgaWYoUFAtPmw9PVApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFJpZ2h0Um90YXRlKFBQUCk7CiAgICAgICAgICAgICAgICBSaWdodFJvdGF0ZShQUCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBMZWZ0Um90YXRlKFBQKTsKICAgICAgICAgICAgICAgIFJpZ2h0Um90YXRlKFBQUCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaWYoUFAtPmw9PVApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFJpZ2h0Um90YXRlKFBQKTsKICAgICAgICAgICAgICAgIExlZnRSb3RhdGUoUFBQKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIExlZnRSb3RhdGUoUFBQKTsKICAgICAgICAgICAgICAgIExlZnRSb3RhdGUoUFApOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcm9vdD1QOwp9CnZvaWQgSW5zZXJ0KHBhaXI8aW50LCBpbnQ+IHYsaW50IGFuc3YsaW50IGFuc2kpCnsKICAgIE5vZGUgKlQ9cm9vdDsKICAgIGlmKCFUKQogICAgewogICAgICAgIHJvb3Q9KE5vZGUqKSBtYWxsb2Moc2l6ZW9mKE5vZGUpKTsKICAgICAgICByb290LT5sPU5VTEw7CiAgICAgICAgcm9vdC0+cj1OVUxMOwogICAgICAgIHJvb3QtPnA9TlVMTDsKICAgICAgICByb290LT52PXY7CiAgICAgICAgcm9vdC0+c3o9MTsKICAgICAgICByb290LT5hbnN2PWFuc3Y7CiAgICAgICAgcm9vdC0+YW5zaT1hbnNpOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIHdoaWxlKFQpCiAgICB7CiAgICAgICAgaWYodiA8IChULT52KSApCiAgICAgICAgewogICAgICAgICAgICBpZihULT5sKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBUPVQtPmw7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFQtPmw9KE5vZGUgKiltYWxsb2Moc2l6ZW9mKE5vZGUpKTsKICAgICAgICAgICAgICAgIFQtPmwtPmw9TlVMTDsKICAgICAgICAgICAgICAgIFQtPmwtPnI9TlVMTDsKICAgICAgICAgICAgICAgIFQtPmwtPnA9VDsKICAgICAgICAgICAgICAgIFQtPmwtPnY9djsKICAgICAgICAgICAgICAgIFQtPmwtPmFuc3Y9YW5zdjsKICAgICAgICAgICAgICAgIFQtPmwtPmFuc2k9YW5zaTsKICAgICAgICAgICAgICAgIFQtPmwtPnN6PTE7CiAgICAgICAgICAgICAgICBUPVQtPmw7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpZihULT5yKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBUPVQtPnI7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFQtPnI9KE5vZGUgKiltYWxsb2Moc2l6ZW9mKE5vZGUpKTsKICAgICAgICAgICAgICAgIFQtPnItPmw9TlVMTDsKICAgICAgICAgICAgICAgIFQtPnItPnI9TlVMTDsKICAgICAgICAgICAgICAgIFQtPnItPnA9VDsKICAgICAgICAgICAgICAgIFQtPnItPnY9djsKICAgICAgICAgICAgICAgIFQtPnItPmFuc3Y9YW5zdjsKICAgICAgICAgICAgICAgIFQtPnItPmFuc2k9YW5zaTsKICAgICAgICAgICAgICAgIFQtPnItPnN6PTE7CiAgICAgICAgICAgICAgICBUPVQtPnI7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIE5vZGUqIHRvc3BsYXk9VDsKICAgIHdoaWxlKFQpCiAgICB7CiAgICAgICAgVXBkYXRlU2l6ZShUKTsKICAgICAgICBUPVQtPnA7CiAgICB9CiAgICBTcGxheSh0b3NwbGF5KTsKfQogCk5vZGUqIEZpbmQocGFpcjxpbnQsaW50PiB2KQp7CiAgICBOb2RlICpUPXJvb3Q7CiAgICB3aGlsZShUKQogICAgewogICAgICAgIGlmKHY9PShULT52KSkKICAgICAgICB7CiAgICAgICAgICAgIFNwbGF5KFQpOwogICAgICAgICAgICByZXR1cm4gVDsKICAgICAgICB9CiAgICAgICAgaWYodjwgKFQtPnYpKQogICAgICAgIHsKICAgICAgICAgICAgaWYoVC0+bCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgVD1ULT5sOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgU3BsYXkoVCk7CiAgICAgICAgICAgICAgICByZXR1cm4gTlVMTDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpZihULT5yKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBUPVQtPnI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBTcGxheShUKTsKICAgICAgICAgICAgICAgIHJldHVybiBOVUxMOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIE5VTEw7Cn0KIAp2b2lkIEVyYXNlKE5vZGUgKlQpCnsKICAgIFNwbGF5KFQpOwogICAgIAogICAgaWYoVC0+bCkKICAgIHsKICAgICAgICByb290PVQtPmw7CiAgICAgICAgTm9kZSAqeD1yb290OwogICAgICAgIHdoaWxlKHgtPnIpIHg9eC0+cjsKICAgICAgICB4LT5yPVQtPnI7CiAgICAgICAgaWYoVC0+cikgVC0+ci0+cD14OwogICAgICAgIHdoaWxlKHgtPnApCiAgICAgICAgewogICAgICAgICAgICBVcGRhdGVTaXplKHgpOwogICAgICAgICAgICB4PXgtPnA7CiAgICAgICAgfQogICAgfQogICAgZWxzZQogICAgICAgIHJvb3Q9VC0+cjsKICAgIGZyZWUoVCk7CiAgICBpZihyb290KXJvb3QtPnA9TlVMTDsKfQogCk5vZGUqIGZpbmRLdGgoTm9kZSAqVCxpbnQgSykKewogICAgaW50IHN6PTA7CiAgICBpZihULT5sKSBzej1ULT5sLT5zejsKICAgIGlmKHN6PT1LKSByZXR1cm4gVDsKICAgIGlmKHN6PkspCiAgICAgICAgcmV0dXJuIGZpbmRLdGgoVC0+bCxLKTsKICAgIGVsc2UKICAgICAgICByZXR1cm4gZmluZEt0aChULT5yLEstc3otMSk7Cn0KTm9kZSogZmluZEt0aChpbnQgSykKewogICAgTm9kZSogS3RoPWZpbmRLdGgocm9vdCxLKTsKICAgIFNwbGF5KEt0aCk7CiAgICByZXR1cm4gS3RoOwp9CmludCBSOwpjb25zdCBpbnQgTUFYTj0xMzEwNzI7CmludCBpZHhbTUFYTioyXTsKaW50IGdldG1heChpbnQgbCxpbnQgcikKewogICAgbCs9TUFYTjsKICAgIHIrPU1BWE47CiAgICBpbnQgYW5zPTA7CiAgICB3aGlsZShsPD1yKQogICAgewogICAgICAgIGlmKGwlMj09MSkKICAgICAgICAgICAgYW5zPW1heChhbnMsaWR4W2wrK10pOwogICAgICAgIGlmKHIlMj09MCkKICAgICAgICAgICAgYW5zPW1heChhbnMsaWR4W3ItLV0pOwogICAgICAgIGwvPTI7CiAgICAgICAgci89MjsKICAgIH0KICAgIHJldHVybiBhbnM7Cn0Kdm9pZCBRdWVyeShpbnQgQSxpbnQgQikgLy9mcm9tIEF0aCBOb2RlIHRvIEJ0aCBOb2RlICgwLWJhc2VkKQp7CiAgICBpbnQgZmluZGNvdW50PUItQSsxOwogICAgTm9kZSAqQXRoPWZpbmRLdGgoQSk7CiAgICBOb2RlICpCdGg9ZmluZEt0aChCKTsKICAgIC8vcHJpbnRmKCIlZCAlZCAlZCAlZFxuIixBLEIsKEF0aC0+dikuZmlyc3QsKEJ0aC0+dikuZmlyc3QpOwogICAgaW50IGFuc3Y9LTE7CiAgICBpbnQgYW5zaT0tMTsKICAgIHBhaXI8aW50LGludD4gdj1tYWtlX3BhaXIoKEF0aC0+dikuZmlyc3QsKEJ0aC0+dikuc2Vjb25kKTsKICAgIC8vcHJpbnRmKCIlZFxuIixyb290LT5zeik7CiAgICBmb3IoaW50IGk9MDtpPGZpbmRjb3VudDtpKyspCiAgICB7CiAgICAvLyAgcHJpbnRmKCIlZCAlZFxuIixyb290LT5zeixBKTsKICAgICAgICBOb2RlICpBdGg9ZmluZEt0aChBKTsKICAgICAgICBpZihhbnN2IDwgKEF0aC0+YW5zdikpCiAgICAgICAgewogICAgICAgICAgICBhbnN2PUF0aC0+YW5zdjsKICAgICAgICAgICAgYW5zaT1BdGgtPmFuc2k7CiAgICAgICAgfQogICAgICAgIC8vcHJpbnRmKCIlZFxuIixyb290LT5zeik7CiAgICAgICAgRXJhc2UoQXRoKTsKICAgIH0KICAgIC8vcHV0cygib2siKTsKICAgIGludCBhbnM9Z2V0bWF4KHYuZmlyc3Qsdi5zZWNvbmQtMSk7CiAgICAgCiAgICBpZihhbnM8UikgYW5zdisrOwogICAgSW5zZXJ0KHYsYW5zdixhbnNpKTsKfQogCiAKaW50IEdldEJlc3RQb3NpdGlvbihpbnQgTiwgaW50IEMsIGludCBSLCBpbnQgKkssIGludCAqUywgaW50ICpFKQp7CiAgICA6OlI9UjsKICAgIGZvcihpbnQgaT0wO2k8TjtpKyspCiAgICAgICAgSW5zZXJ0KG1ha2VfcGFpcihpLGkpLDAsaSk7CiAgICBmb3IoaW50IGk9MDtpPE4tMTtpKyspCiAgICAgICAgaWR4W01BWE4raV09S1tpXTsKICAgIGZvcihpbnQgaT1NQVhOLTE7aT49MTtpLS0pCiAgICAgICAgaWR4W2ldPW1heChpZHhbMippXSxpZHhbMippKzFdKTsKICAgIGZvcihpbnQgaT0wO2k8QztpKyspCiAgICAgICAgUXVlcnkoU1tpXSxFW2ldKTsKICAgIHJldHVybiByb290LT5hbnNpOyAgCn0=