import sys input=sys.stdin.readline class SegmentTree(): def __init__(self,size,f=lambda x,y:x+y,default=0): self.size=pow(2,(size-1).bit_length()) self.f=f self.default=default self.data=[default]*(self.size*2) # list[i]をxに更新 def update(self,i,x): i+=self.size self.data[i]=x while i: i>>=1 self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # はじめの構築をO(N)で行う def init_build(self,ary): n=len(ary) for i in range(n): self.data[i+self.size]=ary[i] for i in reversed(range(self.size)): self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # 区間[l,r)へのクエリ def query(self,l,r): l,r=l+self.size,r+self.size lret,rret=self.default,self.default while l>=1 r>>=1 return self.f(lret,rret) def get(self,i): return self.data[self.size+i] n=int(input()) xary=list(map(int,input().split())) q=int(input()) lrx=[list(map(int,input().split())) for _ in range(q)] events=[] for i,x in enumerate(xary): events.append([x,i]) for i,(l,r,x) in enumerate(lrx): events.append([x,i+n]) events.sort(key=lambda x:x[0]) inf=float('inf') mxst=SegmentTree(n,max,-inf) mnst=SegmentTree(n,min,inf) mnst.init_build(xary) ret=[None]*q idx=0 for x,i in events: if i