简单易学的平衡树，虽然随机值要靠rp，但一般来说还是不会被卡的。
treap=tree+heap，treap有两个关键值，id和权值。
一般的二叉排序树难以维持自身平衡，容易退化成链，所以就有了id值。
id靠随机，对我们来说无实际意义，由堆序维护，听起来有点搞笑，但确实在大多数情况下能维护平衡。
w是节点自身属性，对我们来说有实际意义，遵循二叉排序树的规则，即根节点左子树均小于根，右子树均大于根，递归定义。
由于treap兼有二者特点，所以维护的时候，不能单一的按tree或heap来，于是诞生了旋转的操作，既能维护堆序，又能维护树序。
在treap中分为左旋和右旋两种：
右旋
1 1
\ \
2 3
/ \ ——————> / \
3 4 5 2
/ \
5 4
左旋
1 1
\ \
2 4
/ \ ——————> / \
3 4 2 5
\ /
5 3
插入，先按二叉排序树插入，再维护id堆序（左旋，右旋实现,同时维护信息）
删除，找到指定节点，不断通过左旋右旋下沉，下沉至链节点（至少有一个子树为空）用其不为空子节点代替
基本操作就这些，还附带找k大，k小值等等操作
推荐模板http://blog.csdn.net/cjoilmd/article/details/6629062
lmd同学借助splay模板，写的非递归版treap，同时还有易错点。
总的来说，调试起来不是一般的麻烦，还是左偏树好调试。
const maxr=100000;
var n,m,ss,ll,rr:longint;
size,l,r,w,id,rt,a:array[0..200000]of longint;
x,y,q,z,ans:array[0..500000]of longint;
check:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y)
end;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y)
end;
procedure right(x:longint);
var y,z:longint;
begin
y:=rt[x];z:=rt[y];
if l[z]=y then l[z]:=x else r[z]:=x;rt[x]:=z;
l[y]:=r[x];rt[r[x]]:=y;
r[x]:=y;rt[y]:=x;
size[x]:=size[y];
size[y]:=size[l[y]]+size[r[y]]+1
end;
procedure left(x:longint);
var y,z:longint;
begin
y:=rt[x];z:=rt[y];
if l[z]=y then l[z]:=x else r[z]:=x;rt[x]:=z;
r[y]:=l[x];rt[l[x]]:=y;
l[x]:=y;rt[y]:=x;
size[x]:=size[y];
size[y]:=size[l[y]]+size[r[y]]+1
end;
function ori(x,y:longint):longint;
begin
inc(ss);id[ss]:=random(maxr);
w[ss]:=x;size[ss]:=1;
l[ss]:=0;r[ss]:=0;rt[ss]:=y;
ori:=ss
end;
procedure ins(p:longint);
var x:longint;
begin
x:=1;
while true do begin
inc(size[x]);
if p>w[x] then begin
if r[x]=0 then begin r[x]:=ori(p,x);x:=r[x];break end
else x:=r[x]
end
else begin
if l[x]=0 then begin l[x]:=ori(p,x);x:=l[x];break end
else x:=l[x]
end
end;
while id[x]<id[rt[x]] do
if l[rt[x]]=x then right(x) else left(x)
end;
procedure low(x:longint);
var ll,rr:longint;
begin
ll:=l[x];rr:=r[x];
if id[ll]<id[rr] then right(ll) else left(rr)
end;
procedure del(p:longint);
var x,y,z:longint;
begin
x:=1;
while w[x]<>p do if w[x]<p then x:=r[x] else x:=l[x];
id[x]:=maxlongint;
while (l[x]<>0)and(r[x]<>0) do low(x);
y:=rt[x];
if l[x]=0 then z:=r[x] else z:=l[x];
if l[y]=x then l[y]:=z else r[y]:=z;
if z<>0 then rt[z]:=y;
while id[y]<>-maxlongint do begin
dec(size[y]);
y:=rt[y]
end;
dec(size[y])
end;
function findmin(q:longint):longint;
var x:longint;
begin
x:=1;inc(q);
while true do begin
if q=size[l[x]]+1 then exit(w[x])
else if q<=size[l[x]] then x:=l[x]
else begin
q:=q-size[l[x]]-1;
x:=r[x]
end
end
end;
procedure work;
var i,j:longint;
begin
rr:=0;x[0]:=x[1];
for i:=1 to m do begin
for j:=x[i-1] to min(x[i]-1,y[i-1]) do del(a[j]);
for j:=max(rr+1,x[i]) to y[i] do ins(a[j]);
ans[z[i]]:=findmin(q[i]);rr:=y[i]
end
end;
procedure qsort(l,r:longint);
var i,j,xx,yy,c:longint;
begin
i:=l;j:=r;xx:=x[(l+r)>>1];yy:=y[(l+r)>>1];
repeat
while (x[i]<xx)or((x[i]=xx)and(y[i]<yy)) do inc(i);
while (xx<x[j])or((xx=x[j])and(yy<y[j])) do dec(j);
if not(i>j) then begin
c:=x[i];x[i]:=x[j];x[j]:=c;
c:=y[i];y[i]:=y[j];y[j]:=c;
c:=q[i];q[i]:=q[j];q[j]:=c;
c:=z[i];z[i]:=z[j];z[j]:=c;
inc(i);dec(j)
end
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j)
end;
procedure init;
var i:longint;
begin
readln(n,m);
for i:=1 to n do read(a[i]);readln;
for i:=1 to m do begin
readln(x[i],y[i],q[i]);
z[i]:=i
end;
qsort(1,m);
id[1]:=-maxlongint;w[1]:=-maxlongint;ss:=1;
size[0]:=0;
work;
for i:=1 to m do writeln(ans[i])
end;
begin
randomize;
init
end.