1 var  2    i,j,k,l,m,n,head,ts:longint;f1:text;  3    a,b,fix,lef,rig:array[0..500000] of longint;  4 procedure lt(var x:longint);inline;  5           var f,r:longint;  6           begin  7                if (x=0) or (rig[x]=0) then exit;  8                f:=x;r:=rig[x];  9                b[r]:=b[f]; 10                b[f]:=b[lef[f]]+1+b[LEF[R]]; 11                rig[f]:=lef[r]; 12                lef[r]:=f; 13                x:=r; 14           end; 15 procedure rt(var x:longint);inline; 16           var f,l:longint; 17           begin 18                if (x=0) or (lef[x]=0) then exit; 19                f:=x;l:=lef[x]; 20                b[l]:=b[f]; 21                b[f]:=b[rig[f]]+1+b[rig[l]]; 22                lef[f]:=rig[l]; 23                rig[l]:=f; 24                x:=l; 25           end; 26 FUNCTION max(x,y:longint):longint;inline; 27          begin 28               if x>y then max:=x else max:=y; 29          end; 30 function min(x,y:longint):longint;inline; 31          begin 32               if x<y then min:=x else min:=y; 33          end; 34 procedure ins(var head:longint;x:longint); 35           begin 36                if head=0 then 37                   begin 38                        head:=x; 39                        exit; 40                   end; 41                if a[x]<a[head] then 42                   begin 43                        if lef[head]=0 then lef[head]:=x else ins(lef[head],x); 44                        b[head]:=b[lef[head]]+b[rig[head]]+1; 45                        if fix[lef[head]]<fix[head] then rt(head); 46                   end 47                else 48                    begin 49                         if rig[head]=0 then rig[head]:=x else ins(rig[head],x); 50                         b[head]:=b[lef[head]]+b[rig[head]]+1; 51                         if fix[rig[head]]<fix[head] then lt(head); 52                    end; 53           end; 54 function getp(head,x:longint):longint; 55          begin 56               if head=0 then exit(0); 57               if a[head]=x then exit(head); 58               if a[head]>x then exit(getp(lef[head],x)) else exit(getp(rig[head],x)); 59          end; 60 procedure del(var head:longint); 61           var i,j,k,l,f,r:longint; 62           begin 63                if head=0 then exit; 64                if (lef[head]=0) then 65                   begin 66                        b[head]:=b[rig[head]]; 67                        head:=rig[head]; 68                        exit; 69                   end; 70                if rig[head]=0 then 71                   begin 72                        b[head]:=b[lef[head]]; 73                        head:=lef[head]; 74                        exit; 75                   end; 76                if fix[lef[head]]>fix[rig[head]] then 77                   begin 78                        lt(head); 79                        del(lef[head]); 80                        b[head]:=b[lef[head]]+b[rig[head]]+1; 81                   end 82                else 83                    begin 84                         rt(head); 85                         del(rig[head]); 86                         b[head]:=b[lef[head]]+b[rig[head]]+1; 87                    end; 88           end; 89 procedure det(var head,x:longint); 90           begin 91                if head=0 then exit; 92                if x=head then 93                   begin 94                        del(head); 95                        b[head]:=b[lef[head]]+b[rig[head]]+1; 96                        exit; 97                   end; 98                if lef[head]=x then 99                   begin100                        del(lef[head]);101                        b[head]:=b[lef[head]]+b[rig[head]]+1;102                        exit;103                   end;104                if rig[head]=x then105                   begin106                        del(rig[head]);107                        b[head]:=b[lef[head]]+b[rig[head]]+1;108                        exit;109                   end;110                if a[x]<a[head] then det(lef[head],x) else det(rig[head],x);111                b[head]:=b[lef[head]]+b[rig[head]]+1;112           end;113 procedure showoff(head:longint);114           begin115                if head=0 then exit;116                showoff(lef[head]);117                write(a[head],‘ ‘);118                showoff(rig[head]);119           end;120 function getrank(head,x:longint):longint;121          var k:longint;122          begin123               if head=0 then exit(-1);124               if x=a[head] then   //亲们注意了，就是这个地方坑了我好久啊啊啊啊啊啊125                  begin126                       k:=getrank(lef[head],x);127                       if k=-1 then exit(b[lef[head]]+1) else exit(k);128                  end129               else130                   begin131                        if x<a[head] then132                           begin133                                exit(getrank(lef[head],x));134                           end135                        else136                            begin137                                 k:=getrank(rig[head],x);138                                 if k=-1 then exit(-1) else exit(b[lef[head]]+1+k);139                            end;140                   end;141          end;142 function rankget(head,x:longint):longint;143          begin144               if head=0 then exit(maxlongint);145               if (b[lef[head]]+1)=x then exit(a[head]);146               if (b[lef[head]]+1)<x then exit(rankget(rig[head],x-1-b[lef[head]])) else exit(rankget(lef[head],x))147          end;148 function getsuc(head,x:longint):longint;149          begin150               if (head=0) then exit(+maxlongint);151               if (a[head]<=x) then exit(getsuc(rig[head],x)) else exit(min(a[head],getsuc(lef[head],x)));152          end;153 function getpre(head,x:longint):longint;154          begin155               if (head=0) then exit(-maxlongint);156               if (a[head]>=x) then exit(getpre(lef[head],x)) else exit(max(a[head],getpre(rig[head],x)));157          end;158 159 begin160      m:=0;head:=0;161      randomize;162      readln(n);163      for i:=1 to  n do164          begin165               read(l);166               case l of167                    1:begin168                           readln(j);169                           inc(m);170                           a[m]:=j;171                           fix[m]:=random(maxlongint);172                           lef[m]:=0;rig[m]:=0;b[m]:=1;173                           ins(head,m);174                    end;175                    2:begin176                           readln(j);177                           k:=getp(head,j);178                           det(head,k);179                           l:=0;180                    end;181                    3:BEGIN182                           readln(j);183                           k:=getrank(head,j);184                           writeln(k);185                    end;186                    4:begin187                           readln(j);188                           writeln(rankget(head,j));189                    end;190                    5:begin191                           readln(j);192                           writeln(getpre(head,j));193                    end;194                    6:begin195                           readln(j);196                           writeln(getsuc(head,j));197                    end;198               end;199 200               l:=0;201          end;202          readln;203 end.