{
  Solution for CEOI 2003 Task "The race"
  Author: Tobias Thierer <ceoi@tobias-thierer.de>
}

program therace;

const maxCoord     = 1000000;
      maxShips     =  250000;
      maxOvertakes =   10000; { max. # lines to output }
      maxSpeed     =      99;
      minSpeed     =       1;
      minCoord     =       0;
      modulo       = 1000000;

      debug        = false;
      assertions   = true;
      
      maxHeapsize  =  maxShips;

      inname       = 'therace.in';
      outname      = 'therace.out';
      
      NOT_IN_HEAP = -1;

type TRational = object
                 public
                   constructor init(n,d:Longint);
                   destructor done;
                   function equalTo(r:TRational):Boolean;
                   function smallerThan(r:TRational):Boolean;
                   numerator, denominator: Longint;
                 private
                   procedure normalize;
                   function gcd(a,b:Longint):Longint;
                 end;
     TShip = record
               startPos : Longint;
               speed    : Longint;
               shipNum  : Longint;
             end;
     TOvertake = record
                   time: TRational; { overtake time in seconds since start }
                   overtakerRank: Longint { 1 (last Ship) .. n-1 (course leader) }
                 end; { 12 Bytes }


var ships : array[1..maxShips] of TShip;     { 250.000 * 12 = 3 MBytes }
    heap  : array[1..maxHeapsize] of TOvertake; { 250.000 * 12 = 3 MBytes}
    
    { attention: index is the ship number, not the relative position on the course }
    posInHeap : array[1..maxShips] of Longint; { 1 MByte } 
    heapSize : Longint;
    numShips : Longint;
    lastOvertakingRank,               { rank at time just before overtake }
    lastOvertakingShip   : Longint;   { number of the overtaking ship }
    lastOvertakingTime   : TRational;
    numOvertakes         : Longint;
    currOvertakerRank    : Longint;
    currTime             : TRational;
    outf                 : Text;
    synchronousOvertakes : Boolean; { check if two overtakes appeared at the same time }

{ ----------------------------------------------------------------------- }

function intToString(i:integer):string;
var s:String;
begin str(i,s); intToString:=s end;

procedure assert(b:Boolean;msg:String);
begin
  if (assertions and (not b)) then begin
    writeln('ASSERTION FAILED: ', msg);
    halt;
  end;
end;

constructor TRational.init(n,d:Longint);
begin numerator:=n; denominator:=d; normalize; end;

destructor TRational.done;
begin end;

function TRational.equalTo(r:TRational):Boolean;
begin
  equalTo := ((numerator = r.numerator) and (denominator = r.denominator))
end;

function TRational.smallerThan(r:TRational):Boolean;
begin
  smallerThan := (numerator*r.denominator < denominator*r.numerator)
end;

{ cancel down and force unique, well-defined representation }
procedure TRational.normalize;
var aux:Longint;
begin
  aux := gcd(numerator, denominator);
  numerator := numerator div aux;
  denominator := denominator div aux;
  if denominator < 0 then begin { only numerator may be negative }
    numerator   := - numerator;
    denominator := - denominator;
  end;
  if numerator=0 then denominator:=1;
end;

{ greatest common divisor of a and b }
function TRational.gcd(a,b:Longint):Longint;
var tmp:Longint;
begin
  if (a < b) then begin tmp := a; a := b; b:= tmp end; { swap }
  if (b=0) then gcd := a else gcd := gcd(b, a mod b);
end;

{ ----------------------------------------------------------------------- }

function heapSmaller(idxA, idxB:Longint):Boolean;
begin
  heapSmaller :=  (heap[idxA].time.smallerThan(heap[idxB].time))
               or (   (heap[idxA].time.equalTo(heap[idxB].time))
                   and(heap[idxA].overtakerRank < heap[idxB].overtakerRank));
end;


procedure heapXchg(idxA, idxB:Longint);
var tmp:TOvertake;
begin
  tmp:=heap[idxA]; heap[idxA]:=heap[idxB]; heap[idxB]:=tmp;
  posInHeap[ships[heap[idxA].overtakerRank].shipNum] := idxA;
  posInHeap[ships[heap[idxB].overtakerRank].shipNum] := idxB;
end;

procedure heapUp(pos:Longint);
begin
  if (pos < 1) or (pos > heapSize) then exit;
  while (pos > 1) and heapSmaller(pos, pos div 2) do begin
    heapXchg(pos, pos div 2);
    pos := pos div 2;
  end;
end;

procedure heapDown(pos:Longint);
var newPos : Longint;
begin  
  if (pos < 1) or (pos > heapSize) then exit;
  newPos := pos;
  repeat
    pos := newPos;
    if (2*pos <= heapSize) and (heapSmaller(2*pos, newPos)) then newPos:=2*pos;
    if (2*pos+1 <= heapSize) and (heapSmaller(2*pos+1, newPos)) then newPos:=2*pos+1;
    heapXchg(pos, newPos);
  until pos = newPos;
end;
    

procedure heapPut(time:TRational; overtakerRank:Longint);
begin
  inc(Heapsize);
  heap[heapsize].time := time;
  heap[heapsize].overtakerRank := overtakerRank;
  posInHeap[ships[overtakerRank].shipNum] :=  heapSize;
  heapUp(heapSize);
end;

procedure heapGet(var time:TRational; var overtakerRank:Longint);
begin
  time := heap[1].time;
  overtakerRank := heap[1].overtakerRank;
  heapXchg(1, heapSize);
  posInHeap[ships[overtakerRank].shipNum] := NOT_IN_HEAP;
  // if debug then writeln(ships[overtakerRank].shipNum,' not scheduled any more');
  dec(heapSize);
  if heapSize > 0 then heapDown(1);
end;

{ ----------------------------------------------------------------------- }

procedure readShips;
var inf : Text;
    i   : Longint;
begin
  assign(inf, inname);
  reset(inf);
  readln(inf, numShips);
  assert(numShips <= maxShips, 'too many ships');
  for i:=1 to numShips do with ships[i] do begin
    readln(inf, startPos, speed);
    assert((startPos <= maxCoord) and (startPos >= minCoord), 'illegal start pos');
    assert((speed <= maxSpeed) and (speed >= minSpeed),'illegal speed: ' + intToString(speed));
    shipNum := i;
  end;
  close(inf);
end;

{ Checks if ship at index (overtaker) will overtake the one in front of it.
  If so, it puts the overtake event into the heap. }
procedure checkOvertake(overtakerRank:Longint);
var deltaSpeed, deltaPos : Longint;
    time             : TRational;
    overtakerShipnum : Longint;
    overtakerHeappos : Longint;
begin
  if (overtakerRank < 1) or (overtakerRank >= numShips) then exit;
  deltaSpeed := ships[overtakerRank].speed - ships[overtakerRank+1].speed;
  deltaPos := ships[overtakerRank+1].startPos - ships[overtakerRank].startPos;
  if ((deltaSpeed > 0) and (deltaPos > 0)) then begin
    overtakerShipnum := ships[overtakerRank].shipNum;
    overtakerHeapPos := posInHeap[overtakerShipnum];
    time.init(deltaPos, deltaSpeed);
    assert(overtakerHeapPos = NOT_IN_HEAP, 'overtaker ' + intToString(overtakerShipNum) + ' already in heap');
    // if debug then writeln('scheduled overtake ', ships[overtakerRank].shipNum,' ', ships[1+overtakerRank].shipNum);
    heapPut(time, overtakerRank);
  end;
end;

procedure deleteFromHeap(shipNum:Longint);
var heapPos : Longint;
begin
  heapPos := posInHeap[shipNum];
  if (heapPos <> NOT_IN_HEAP) then begin
    heapXchg(heapPos, heapSize);
    posInHeap[shipNum] := NOT_IN_HEAP;
    // if debug then writeln(shipNum,' not scheduled any more');
    dec(heapSize);
    heapDown(heapPos);  // at most one of these two will change the heap
    heapUp(heapPos);
  end;
end;

{ change the order of two adjacent ships in ships[] }
procedure executeOvertake(idxA:Longint);
var idxB    : Longint;
    tmpShip : TShip;
begin
  // if debug then writeln('Begin Overtake Execution');
  assert(not (    currTime.equalTo(lastOvertakingTime)
              and (ships[idxA].shipNum = lastOvertakingShip)),
         'Three ships at same position at same time');
  assert(not(currTime.smallerThan(lastOvertakingTime)),'Overtakes in wrong time order'); 
  if currTime.equalTo(lastOvertakingTime) then begin
    assert(lastOvertakingRank < idxA, 'Overtakes in wrong position order');
    synchronousOvertakes := true;
  end;
  lastOvertakingTime := currTime;
  lastOvertakingShip := ships[idxA].shipNum;
  lastOvertakingRank := idxA;
  
  idxB := idxA + 1;
  writeln(outf, ships[idxA].shipNum,' ', ships[idxB].shipNum);
  // if debug then writeln(ships[idxA].shipNum,' overtakes ', ships[idxB].shipNum, ', ', heapSize, ' left.');
  inc(numOvertakes);
  {   X --> A,B --> Y }
  
  { delete inactivated overtake events (X,A) and (B,Y) from queue }
  if idxA > 1 then deleteFromHeap(ships[idxA-1].shipNum); 
  deleteFromHeap(ships[idxB].shipNum);
  tmpShip := ships[idxA]; ships[idxA] := ships[idxB]; ships[idxB] := tmpShip;
  { add new active overtake events (X,B) and (A,Y) to queue }
  checkOvertake(idxA-1); 
  checkOvertake(idxB);
  // if debug then writeln('End Overtake Execution');
end;

{ ----------------------------------------------------------------------- }

procedure init;
var i:Longint;
begin
  heapSize := 0;
  numOvertakes := 0;
  synchronousOvertakes := false;
  lastOvertakingShip := -1;
  lastOvertakingTime.init(0,1);
  readShips;
  for i:=1 to numShips do posInHeap[i] := NOT_IN_HEAP;
  for i:=1 to numShips-1 do checkOvertake(i);
end;


{ Counts number of overtakes (calls registerOvertakes() within ship group at
  positions left..right 
  SIDE EFFECT: afterwards, numSlowerThan[i] contains the number of ships at
  positions left..right that are slower than speed i. Runtime: O(n log n). }
procedure subtaskA;
var numWithSpeed,
    numSlowerThan:array[1..maxSpeed+1] of Longint;
    numOvertakes : Longint;
  procedure countOvertakes(left, right:Longint);
  var middle, i, sum : Longint;
  begin
    for i:=1 to maxSpeed do numSlowerThan[i] := 0;
    if left=right then for i:=ships[left].speed+1 to maxSpeed do numSlowerThan[i]:=1;
    if left >= right then exit;
    middle := (left + right) div 2;
    countOvertakes(left, middle);
    countOvertakes(middle+1, right);
    { Now we have calculated the number of overtakes within the two
      halfs. We still need to count the overtakes across these two
      groups. Additionally, numSlowerThan[] currently only contains
      the data for the right half; the left half is still to be
      added. }
    for i:=1 to maxSpeed+1 do numWithSpeed[i] := 0; { in left half }
    for i:=left to middle do begin
      numOvertakes := (numOvertakes + numSlowerThan[ships[i].speed]) MOD modulo; { across-group overtakes }
      inc(numWithSpeed[ships[i].speed]);
    end;
    sum := 0;
    for i:=1 to maxSpeed+1 do begin  { update numSlowerThan[] with ships }
      inc(numSlowerThan[i], sum);    { from left half }
      inc(sum, numWithSpeed[i]);
    end;
  end;
begin
  numOvertakes := 0;
  countOvertakes(1, numShips);
  writeln(outf, numOvertakes);  
end;

{ ----------------------------------------------------------------------- }

begin
  init;
  assign(outf,outname);
  rewrite(outf);
  subtaskA;
  while (heapSize > 0) and (numOvertakes < maxOvertakes) do begin
    heapGet(currTime, currOvertakerRank);
    assert(currOvertakerRank < numShips, 'leading ship overtakes!?');
    executeOvertake(currOvertakerRank);
  end;
  close(outf);
  if debug and synchronousOvertakes then writeln('At least two overtakes appeared at the same time (at different locations)');
end.