import sys from bisect import bisect read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines INF = 1 << 30 def main(V, query): def merge(A, B): return C N = len(V) seg = [None for _ in range(N + N)] for i in range(N): seg[N + i] = [V[i]] for k in range(N - 1, 0, -1): A, B = seg[k + k], seg[k + k + 1] NA, NB = len(A), len(B) i, j = 0, 0 C = [0] * (NA + NB) for c in range(NA + NB): if i == NA: C[c] = B[j] j += 1 elif j == NB: C[c] = A[i] i += 1 else: if A[i] > B[j]: C[c] = B[j] j += 1 else: C[c] = A[i] i += 1 seg[k] = C def nearest(A, x): n = len(A) i = bisect(A, x) v = INF if i > 0: v = x - A[i - 1] if i < n: v = min(v, A[i] - x) return v for L, R, x in query: L -= 1 L += N R += N v = INF while L < R: if L & 1: v = min(v, nearest(seg[L], x)) L += 1 if R & 1: R -= 1 v = min(v, nearest(seg[R], x)) L, R = L >> 1, R >> 1 print(v) N = int(readline()) X = tuple(map(int, readline().split())) Q = int(readline()) m = map(int, read().split()) query = zip(m, m, m) main(X, query)