import sys from collections import deque, Counter import time input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 32 - 1 mod = 998244353 class lazy_segtree(): def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1]) def all_apply(self,k,f): self.d[k]=self.mapping(f,self.d[k]) if (k>i) self.d[p]=x for i in range(1,self.log+1):self.update(p>>i) def get(self,p): assert 0<=p and p>i) return self.d[p] def prod(self,l,r): assert 0<=l and l<=r and r<=self.n if l==r:return self.e l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) sml,smr=self.e,self.e while(l>=1 r>>=1 return self.op(sml,smr) def all_prod(self):return self.d[1] def apply_point(self,p,f): assert 0<=p and p>i) self.d[p]=self.mapping(f,self.d[p]) for i in range(1,self.log+1):self.update(p>>i) def apply(self,l,r,f): assert 0<=l and l<=r and r<=self.n if l==r:return l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) l2,r2=l,r while(l>=1 r>>=1 l,r=l2,r2 for i in range(1,self.log+1): if (((l>>i)<>i) if (((r>>i)<>i) def max_right(self,l,g): assert 0<=l and l<=self.n assert g(self.e) if l==self.n:return self.n l+=self.size for i in range(self.log,0,-1):self.push(l>>i) sm=self.e while(1): while(l%2==0):l>>=1 if not(g(self.op(sm,self.d[l]))): while(l>i) sm=self.e while(1): r-=1 while(r>1 and (r%2)):r>>=1 if not(g(self.op(self.d[r],sm))): while(r>i) def get(self,p): assert 0<=p and p>=1 r>>=1 return self.op(sml,smr) def all_prod(self): return self.d[1] def update(self,k): self.d[k]=self.op(self.d[2*k],self.d[2*k+1]) def __str__(self): return str([self.get(i) for i in range(self.n)]) n, q = mi() a = li() LR = [li() for _ in range(q)] ok = [n - 1] * q ng = [-1] * q soa = list(range(n)) soa.sort(key = lambda x: a[x]) def op(s, t): return (max(s[0], s[3] + t[0]), max(t[1], s[1] + t[3]),max(s[2], t[2], s[1] + t[0]), s[3] + t[3]) for _ in range(16): mididx = [[] for _ in range(n)] for i in range(q): if ok[i] - ng[i] > 1: mid = (ok[i] + ng[i]) // 2 mididx[mid].append(i) S = segtree([(1, 1, 1, 1) for _ in range(n)], op, (0,0,0,0)) for x, i in enumerate(soa): S.set(i, (-1, -1, -1, -1)) for v in mididx[x]: P = S.prod(LR[v][0] - 1, LR[v][1]) if P[3] < 0 or P[3] - P[2] + 1 < 0: ok[v] = x else: ng[v] = x soa = sorted(a) for i, v in enumerate(ok): print(soa[v])