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]) 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) S1 = lazy_segtree([i for i in range(n)], min, inf, lambda x, y: x + y, lambda x, y: x + y, 0) S2 = lazy_segtree([i for i in range(n)], max, -inf, lambda x, y: x + y, lambda x, y: x + y, 0) Count = segtree([1] * n, lambda x, y: x + y, 0) for x, i in enumerate(soa): S1.set(i, inf) S2.set(i, -inf) S1.apply(i+1, n, -2) S2.apply(i+1, n, -2) Count[i] -= 2 for v in mididx[x]: if Count[LR[v][0] - 1:LR[v][1]] < 0 or Count[LR[v][0] - 1:LR[v][1]] - (S2.prod(LR[v][0] - 1,LR[v][1]) - S1.prod(LR[v][0] - 1,LR[v][1])) < 0: ok[v] = x else: ng[v] = x soa = sorted(a) for i, v in enumerate(ok): print(soa[v])