{
        treap.pas
        
        Copyright 2010 Borbath Tamas <[email protected]>
        
        This program is free software; you can redistribute it and/or modify
        it under the terms of the GNU General Public License as published by
        the Free Software Foundation; either version 2 of the License, or
        (at your option) any later version.
        
        This program is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.
        
        You should have received a copy of the GNU General Public License
        along with this program; if not, write to the Free Software
        Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
        MA 02110-1301, USA.
}


program treapos;

uses crt;

type treap=^node;
	node=record
	priority,key:integer;
	left,right:treap;
	end;
var a : treap;
	n:integer;
	g:text;
procedure rotleft(var n:treap);
	var t:treap;
	begin
		t:=n^.left;
		n^.left:=t^.right;
		t^.right:=n;
		n:=t;
	end;
procedure rotright(var n:treap);
	var t:treap;
	begin
		t:=n^.right;
		n^.right:=t^.left;
		t^.left:=n;
		n:=t;
	end;

procedure balance(var h:treap);
	begin
		if h^.left<>nil then begin
		if h^.left^.priority < h^.priority then rotleft(h) 
		end
		else if h^.right<>nil then 
			if h^.right^.priority <h^.priority then rotright(h);
	end;

procedure eko(h:treap);
	begin
		if h<>nil then begin eko(h^.left);
		writeln(g,h^.priority);
		eko(h^.right); end;
	end;
	
function search(h:treap;key:integer):integer;
		begin
			if h = nil then search:=0 else 
    if key = h^.key then search:=1 else 
    if key < h^.key then 
       search:=search(h^.left, key)
    else
        search:=search(h^.right, key);
		end;
procedure init;
	begin
		randomize;
		new(a);
		a^.key:=0;
		a^.priority:=0;
		a^.left:=nil;
		a^.right:=nil;
	end;
procedure insert(var h:treap; key,priority:integer);
	begin
		if h=nil then begin
						new(h);
						h^.key:=key;
						h^.priority:=priority;
						h^.left:=nil;
						h^.right:=nil;
					  end else
						begin
							if key>h^.key then insert(h^.right,key,priority)
							else {if key<h^.key then} insert(h^.left,key,priority);
							balance(h);
						end;
	end;
procedure beolvas;
	var f:text;
		i,seged:integer;
		begin
			assign(f,'schi.in');
			reset(f);
			readln(f,n);
			for i:=1 to n do
				begin
				readln(f,seged);
				insert(a,seged,i);
				end;
		end;
BEGIN
 init;
 beolvas;
 assign(g,'schi.out');
 rewrite(g);
eko(a^.right);
close(g);
END.