import sys input = sys.stdin.buffer.readline INF = 10**18 class SegmentTree: """ https://qiita.com/dn6049949/items/afa12d5d079f518de368 から拝借しています。 """ def __init__(self, size, f=lambda x, y: min(x, y), default=10**6): self.size = 2 ** (size - 1).bit_length() self.default = default self.dat = [default] * (self.size * 2) self.f = f def initialize(self, A): for i, a in enumerate(A, self.size): self.dat[i] = a for i in range(self.size - 1, 0, -1): self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1]) def update(self, i, x): i += self.size self.dat[i] = x while i > 0: i >>= 1 self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1]) def query(self, l, r): """半開区間[l,r)""" l += self.size r += self.size lres, rres = self.default, self.default while l < r: if l & 1: lres = self.f(lres, self.dat[l]) l += 1 if r & 1: r -= 1 rres = self.f(self.dat[r], rres) l >>= 1 r >>= 1 res = self.f(lres, rres) return res N = int(input()) X = list(map(int, input().split())) points = [] for i, x in enumerate(X): points.append((x, i)) points.sort() Q = int(input()) queries = [] for i in range(Q): l, r, x = map(int, input().split()) l -= 1 r -= 1 queries.append((i, l, r, x)) queries.sort(key=lambda x: x[3]) ans = [0] * Q seg_smaller = SegmentTree(N, f=lambda x, y: max(x, y), default=-INF) seg_bigger = SegmentTree(N, f=lambda x, y: min(x, y), default=INF) seg_bigger.initialize(X) j = 0 for i, l, r, x in queries: while j < N and points[j][0] < x: seg_bigger.update(points[j][1], INF) seg_smaller.update(points[j][1], points[j][0]) j += 1 ans[i] = min(seg_bigger.query(l, r + 1) - x, x - seg_smaller.query(l, r + 1)) print(*ans, sep="\n")