import sys
input = sys.stdin.readline
n,a=map(int,input().split())
x=list(map(int,input().split()))
class LazySegTree:
 
    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [intv]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        v = 2
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1; v <<= 1
 
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v >> 1
            self.lazy[i-1] = None
 
    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = self.N0 + l; R = self.N0 + r
        v = x
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = v
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = v
                L += 1
            L >>= 1; R >>= 1; v <<= 1
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])
 
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
def segfunc(x, y):
    return x + y
xx=[]
for i in range(n):
  xx.append((x[i],i))
xx.sort()
x.sort()
inv=[0]*n
for i in range(n):
  inv[xx[i][1]]=i
st=LazySegTree(n,segfunc,0)
t=int(input())
from bisect import bisect_left, bisect_right, insort
for i in range(t):
  l,r=map(int,input().split())
  id1=bisect_left(x,l)
  if id1==n:
    continue
  id2=bisect_right(x,r)-1
  st.update(id1,id2+1,i+1)
for i in range(n):
  ans=st.query(inv[i],inv[i]+1)
  if ans==0:
    print(-1)
  else:
    print(ans)