1 const maxn=100000+10; 2 var s,t:array[0..20,0..maxn] of longint; 3     a,b,rk:array[0..maxn] of longint; 4     i,j,n,m,x,y,k:longint; 5 procedure sort(l,r:longint); 6  var i,j,m,temp:longint; 7  begin 8  i:=l;j:=r;x:=a[(i+j)>>1]; 9  repeat10   while b[a[i]]<b[x] do inc(i);11   while b[a[j]]>b[x] do dec(j);12   if i<=j then13    begin14    y:=a[i];a[i]:=a[j];a[j]:=y;15    inc(i);dec(j);16    end;17  until i>j;18  if i<r then sort(i,r);19  if j>l then sort(l,j);20  end;21 procedure init;22  begin23  readln(n,m);24  for i:=1 to n do read(b[i]);25  for i:=1 to n do a[i]:=i;26  sort(1,n);27  end;28 procedure build(h,l,r:longint);29  var i,p,mid:longint;30  begin31  mid:=(l+r)>>1;p:=0;32  for i:=l to r do33   if t[h,i]<=mid then34    begin35     t[h+1,l+p]:=t[h,i];36     inc(p);37     s[h,i]:=p;38    end39   else40    begin41     t[h+1,mid+1+i-p-l]:=t[h,i];42     s[h,i]:=p;43    end;44  if l=r then exit;45  build(h+1,l,mid);46  build(h+1,mid+1,r);47  end;48 function find(h,l,r,x,y,k:longint):longint;49  var ll,rr,mid:longint;50  begin51  if l=r then exit(t[h,l]);52  mid:=(l+r)>>1;53  if l=x then ll:=0 else ll:=s[h,x-1];rr:=s[h,y]-ll;54  if rr>=k then exit(find(h+1,l,mid,l+ll,l+rr+ll-1,k))55  else exit(find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-rr-ll,k-rr));56  end;57 procedure main;58  begin59  for i:=1 to n do t[0,a[i]]:=i;60  build(0,1,n);61  for i:=1 to m do62   begin63   readln(x,y,k);64   writeln(b[a[find(0,1,n,x,y,k)]]);65   end;66  end;67 begin68  assign(input,‘input.txt‘);assign(output,‘output.txt‘);69  reset(input);rewrite(output);70  init;71  main;72  close(input);close(output);73 end.

 1 var  s,t:array[0..20,0..200000] of longint; 2      a,rk:array[0..200000] of longint; 3      i,n,m,x,y,k,j:longint; 4  procedure sort(l,r:longint); 5  var i,j,m,temp:longint; 6  begin 7  i:=l;j:=r;m:=a[(i+j)>>1]; 8  repeat 9   while a[i]<m do inc(i);10   while a[j]>m do dec(j);11   if i<=j then12    begin13    temp:=a[i];a[i]:=a[j];a[j]:=temp;14    inc(i);dec(j);15    end;16  until i>j;17  if i<r then sort(i,r);18  if j>l then sort(l,j);19  end;20   procedure init;21    begin22      readln(n,m);23      for i:=1 to n do read(a[i]);t[0]:=a;24      sort(1,n);25    end;26  procedure build(h,l,r:longint);27   var  mid,i,lp,rp,lm:longint;28   begin29   mid:=(l+r)>>1;lm:=mid-l+1;lp:=l;rp:=mid+1;30   for i:=l to mid do31    if a[i]<a[mid] then dec(lm);32   for i:=l to r do33    begin34    if i=l then s[h,i]:=0 else s[h,i]:=s[h,i-1];35    if t[h,i]=a[mid] then36     begin37     if lm<>0 then38      begin39      dec(lm);inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp);40      end41     else begin t[h+1,rp]:=t[h,i];inc(rp);end;42     end43    else44     if t[h,i]<a[mid] then begin inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp);end45    else begin t[h+1,rp]:=t[h,i];inc(rp);end;46    end;47   if l=r then exit;48   build(h+1,l,mid);49   build(h+1,mid+1,r);50   end;51  function find(h,l,r,x,y,k:longint):longint;52   var mid,ll,rr:longint;53   begin54   if l=r then exit(t[h,l]);55   mid:=(l+r)>>1;56   if l=x then ll:=0 else ll:=s[h,x-1];rr:=s[h,y]-ll;57   if rr>=k then exit(find(h+1,l,mid,l+ll,l+ll+rr-1,k))58   else exit(find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-ll-rr,k-rr));59   end;60  procedure main;61   begin62    build(0,1,n);63    for i:=1 to m do64     begin65      readln(x,y,k);66      writeln(find(0,1,n,x,y,k));67     end;68   end;69 begin70   init;71   main;72 end.73