#include <cstdio>
#include <algorithm>

using namespace std;

#define dummy NULL

struct node{
 node *l, *r;
 int v, p, s;
 node( int _v = 0 ) { l = r = dummy; v = _v; p = rand(); s = 1; }
};


struct Treap{
 node *root;
 Treap( ) { root = dummy; }

 inline int getp( node *x ) { if( x == dummy ) return 0; else return x->p; }
 inline int gets( node *x ) { if( x == dummy ) return 0; else return x->s; }
 inline void rebuild( node *&x ) { if( x != dummy ) x->s = gets( x->l )+gets( x->r )+1; }

 inline void rot_r( node *&x ) { node *y = x->l; x->l = y->r; y->r = x; rebuild( x->r ); rebuild( x ); x = y; }
 inline void rot_l( node *&x ) { node *y = x->r; x->r = y->l; y->l = x; rebuild( x->l ); rebuild( x ); x = y; }

 void insert( node *&x, int v ) {
  if( x == dummy ) { x = new node( v ); return; }

  if( x->v > v ) insert( x->l, v );
  else insert( x->r, v );

  if( getp( x->l ) > x->p ) rot_r( x );
  else if( getp( x->r ) > x->p ) rot_l( x );

  rebuild( x );
 }

 void erase( node *&x, int v ) {
  if( gets( x ) == 1 ) { delete x; return; }
  if( x->v == v ) {
    if( getp( x->l ) > getp( x->r ) ) rot_r( x );
    else rot_l( x );
    erase( x, v ); return;
  }

  if( x->v > v ) erase( x->l, v );
  else erase( x->r, v );

  rebuild( x );
 }

 int kth( node *&x, int k ) {
  if( x == dummy ) return -1;
  if( gets( x->l )+1 == k ) return x->v;
  if( gets( x->l ) >= k ) return kth( x->l, k );
  else return kth( x->r, k-gets( x->l )-1 );
 }

}T;

int main( void ) {
 for( int i = 0; i < 100000; ++i )
    T.insert( T.root, i );


 for( int i = 3; i < 100000; ++i ) {
    T.erase( T.root, i );
    printf( "%d %d\n", T.root->v, T.root->s );
 }

 return 0;
}