#WaveletMatrix class BitVector(): def __init__(self,A): self.n = len(A) SA = [0] * (self.n + 1) for i,a in enumerate(A): SA[i+1] = SA[i] + a self.SA = SA def rank1(self,r): return self.SA[r] def rank0(self,r): return r - self.SA[r] def select0(self,k): l,r = 0,len(self,SA) if not k < r - 1 - self.SA[r-1]: return -1 while r - l > 1: m = l + r >> 1 if m - self.SA[m] <= k: l = m else: r = m return l def select1(self,k): l,r = 0,len(self.SA) if not k < self.SA[r-1]: return -1 while r - l > 1: m = l + r >> 1 if self.SA[m] <= k: l = m else: r = m return l class WaveletMatrix(): # s: word size. Ai <= 10**6 なら 20 # Ai <= 10**9 なら 30 ぐらいで # (word size < 1 << s となるよう) def __init__(self,s,A): self.s = s self.A = A self.n = len(A) self.X = [] B = A.copy() for i in reversed(range(s)): mask = 1 << i L = [] R = [] T = [] for a in B: if a & mask: T.append(1) R.append(a) else: T.append(0) L.append(a) vb = BitVector(T) self.X.append((vb.rank0(self.n),vb)) B = L + R self.X = self.X[::-1] def access(self,i): return self.A[i] # A[l,r)内のvalueの数を求める def rank(self,l,r,value): if l >= r:return 0 for i in reversed(range(self.s)): z,vb = self.X[i] if value >> i & 1: l = z + vb.rank1(l) r = z + vb.rank1(r) else: l = vb.rank0(l) r = vb.rank0(r) return r - l def select(self,value,k): #A内のk番目のvalueのindexを返す #value が k個なければ-1を返す if self.rank(0,self.n,value) <= k:return -1 ind = 0 for i in reversed(range(self.s)): z,v = self.X[i] if value >> 1 & 1: ind = z + vb.rank1(ind) else: ind = vb.rank0(int) ind += k for i in range(self.s): z,vb = self.X[i] if ind < z: ind = vb.select0(ind) else: ind = vb.select1(ind-z) return ind def freq_to(self,l,r,value): # 0 <= A[i] < value な 数を求める if not value:return 0 if l >= r:return 0 ret = 0 for i in reversed(range(self.s)): z,vb = self.X[i] if value >> i & 1: ret += vb.rank0(r) - vb.rank0(l) l = z + vb.rank1(l) r = z + vb.rank1(r) else: l = vb.rank0(l) r = vb.rank0(r) return ret def freq(self,l,r,d,u): # d <= A[i] < u なる数を求める if d >= u:return 0 return self.freq_to(l,r,u) - self.freq_to(l,r,d) def quantile(self,l,r,k): # [l,r) のk番目に小さい数の返す # k: 0-index k = 0で一番小さい数を返す if k >= r - l:return -1 ret = 0 for i in reversed(range(self.s)): z,vb = self.X[i] zeros = vb.rank0(r) - vb.rank0(l) if zeros > k: l = vb.rank0(l) r = vb.rank0(r) else: k -= zeros ret |= 1 << i l = z + vb.rank1(l) r = z + vb.rank1(r) return ret def quantile2(self,l,r,k): #[l,r)のk番目に大きい数を返す # k: 0-index return self.quantile(l,r,r-l-k-1) import sys rr = sys.stdin N = int(rr.readline()) X = list(map(int,rr.readline().split())) Q = int(rr.readline()) inf = 10 ** 9 + 5 wm = WaveletMatrix(30,X) for _ in range(Q): l,r,x = map(int,rr.readline().split()) t = wm.freq_to(l-1,r,x+1) ans = inf if t > 0: u = wm.quantile(l-1,r,t-1) ans = x - u if t < r - l + 1 - 2: s = wm.quantile(l-1,r,t) ans = min(ans,s - x) print(ans)