import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: src/cplib/tmpl/sheep.nim
ImportExpand "cplib/tmpl/sheep" <=== "when not declared CPLIB_TMPL_SHEEP:\n    const CPLIB_TMPL_SHEEP* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import heapqueue\n    import streams\n    import deques\n    import bitops\n    import std/lenientops\n    import options\n    #入力系\n    proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n    proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n    proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n    proc si(): string {.inline.} =\n        result = \"\"\n        var c: char\n        while true:\n            c = getchar()\n            if c == ' ' or c == '\\n' or c == '\\255':\n                break\n            result &= c\n    \n    # 出力系\n    # 1. 実際の処理を行う proc (openArray を受け取る)\n    proc print_internal(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: openArray[string]) =\n        for i in 0 ..< args.len:\n            prop.f.write(args[i])\n            if i != args.len - 1:\n                prop.f.write(prop.sepc)\n            else:\n                prop.f.write(prop.endc)\n        if prop.flush:\n            prop.f.flushFile()\n\n    # 2. ユーザーが呼び出すためのインターフェース (varargs を受け取る)\n    proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `$`]) =\n        # varargs は内部では openArray として扱えるので、そのまま渡せる\n        print_internal(prop, args)\n\n    proc print*(args: varargs[string, `$`]) =\n        # こちらも内部用の proc を呼ぶ\n        print_internal((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n    macro getSymbolName(x: typed): string = x.toStrLit\n    macro debug*(args: varargs[untyped]): untyped =\n        when defined(debug):\n            result = newNimNode(nnkStmtList, args)\n            template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n            for i, arg in args:\n                if arg.kind == nnkStrLit:\n                    result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n                else:\n                    result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n                    result.add(quote do: print(prop(), `arg`))\n                if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n                else: result.add(quote do: print(prop(), \"\\n\"))\n        else:\n            return (quote do: discard)\n    #chmin,chmax\n    template `max=`(x, y) =\n        let yVal = y # yが計算式の場合に評価を1回にするため\n        if x < yVal:\n            x = yVal\n\n    template `min=`(x, y) =\n        let yVal = y\n        if x > yVal:\n            x = yVal\n    proc chmin[T](x: var T, y: T):bool=\n        if x > y:\n            x = y\n            return true\n        return false\n    proc chmax[T](x: var T, y: T):bool=\n        if x < y:\n            x = y\n            return true\n        return false\n    #bit演算\n    proc `%`*(x: int, y: int): int =\n        result = x mod y\n        if y > 0 and result < 0: result += y\n        if y < 0 and result > 0: result += y\n    proc `//`*(x: int, y: int): int{.inline.} =\n        result = x div y\n        if y > 0 and result * y > x: result -= 1\n        if y < 0 and result * y < x: result -= 1\n    proc `%=`(x: var int, y: int): void = x = x%y\n    proc `//=`(x: var int, y: int): void = x = x//y\n    proc `**`(x: int, y: int): int = x^y\n    proc `**=`(x: var int, y: int): void = x = x^y\n    proc `^`(x: int, y: int): int = x xor y\n    proc `|`(x: int, y: int): int = x or y\n    proc `&`(x: int, y: int): int = x and y\n    proc `>>`(x: int, y: int): int = x shr y\n    proc `<<`(x: int, y: int): int = x shl y\n    proc `~`(x: int): int = not x\n    proc `^=`(x: var int, y: int): void = x = x ^ y\n    proc `&=`(x: var int, y: int): void = x = x & y\n    proc `|=`(x: var int, y: int): void = x = x | y\n    proc `>>=`(x: var int, y: int): void = x = x >> y\n    proc `<<=`(x: var int, y: int): void = x = x << y\n    proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n    #便利な変換\n    proc `!`(x: char, a = '0'): int = int(x)-int(a)\n    #定数\n    when not declared CPLIB_UTILS_CONSTANTS:\n        const CPLIB_UTILS_CONSTANTS* = 1\n        const INF32*: int32 = 1001000027.int32\n        const INF64*: int = int(3300300300300300491)\n    \n    const INF = INF64\n    #converter\n\n    #range\n    iterator range(start: int, ends: int, step: int): int =\n        var i = start\n        if step < 0:\n            while i > ends:\n                yield i\n                i += step\n        elif step > 0:\n            while i < ends:\n                yield i\n                i += step\n    iterator range(ends: int): int = (for i in 0..<ends: yield i)\n    iterator range(start: int, ends: int): int = (for i in\n            start..<ends: yield i)\n\n    #joinが非stringでめちゃくちゃ遅いやつのパッチ\n    proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n    proc dump[T](arr:seq[seq[T]])=\n        for i in 0..<len(arr):\n            echo arr[i]\n\n    proc sum(slice:HSlice[int,int]):int=\n        return (slice.a+slice.b)*len(slice)//2\n    \n    proc `<`[T](l,r:seq[T]):bool=\n        for i in 0..<min(len(l),len(r)):\n            if l[i] > r[i]:\n                return false\n            elif l[i] < r[i]:\n                return true\n        return len(l) < len(r)\n    \n    # Yes/No\n    proc yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n    proc oo*(b: bool = true): void = yes(not b)\n\n    proc takahashi(b:bool = true) : void = print(if b: \"Takahashi\" else: \"Aoki\")\n    proc aoki(b:bool = true) : void = takahashi(not b)\n\n    template dblock(body: untyped) =\n        when defined(debug):\n            block:\n                body\n"
# source: src/cplib/collections/waveletmatrix.nim
ImportExpand "cplib/collections/waveletmatrix" <=== "when not declared CPLIB_COLLECTIONS_WAVELETMATRIX:\n    const CPLIB_COLLECTIONS_WAVELETMATRIX* = 1\n    when not declared CPLIB_COLLECTIONS_BITVECTOR:\n        const CPLIB_COLLECTIONS_BITVECTOR* = 1\n        import bitops\n        import sequtils\n    \n        type BitVector* = object\n            bits : seq[uint64]\n            csum : seq[int]\n    \n        proc newBitVector*(length:int):BitVector=\n            result.bits = newSeq[uint64]((length+63) div 64 + 1)\n            result.csum = newSeq[int](((length+63) div 64)+1)\n    \n        proc set*(self:var BitVector,idx:int)=\n            self.bits[idx div 64].setBit(idx mod 64)\n    \n        proc build*(self:var BitVector)=\n            for i in 0..<(len(self.bits)-1):\n                self.csum[i+1] = self.csum[i] + popcount(self.bits[i])\n    \n        proc access*(self:var BitVector,idx:int):bool=\n            self.bits[idx div 64].testBit(idx mod 64)\n    \n        proc `[]`*(self:var BitVector,idx:int):bool=\n            self.bits[idx div 64].testBit(idx mod 64)\n        \n        proc rank*(self:var BitVector,idx:int):int=\n            return self.csum[idx div 64] + popcount(self.bits[idx div 64] and ((1u shl (idx and 63)) - 1))\n    \n    \n    import sequtils\n    import bitops\n\n    type WaveletMatrix* = ref object\n        dat : seq[BitVector]\n        H : int\n        N : int\n    \n    proc initWaveletMatrix*(v:seq[int],H:int):WaveletMatrix=\n        var v = v\n        var N = len(v)\n        result = WaveletMatrix(dat:newSeqWith(H,newBitVector(N)),N:N,H:H)\n        var zero,one = newseqwith(N,-1)\n        var a = 0\n        var b = 0\n        for h in countdown(H-1,0,1):\n            for i in 0..<N:\n                if v[i].testBit(h):\n                    one[b] = v[i]\n                    b += 1\n                    result.dat[h].set(i)\n                else:\n                    zero[a] = v[i]\n                    a += 1\n            for i in 0..<a:\n                v[i] = zero[i]\n            for i in 0..<b:\n                v[a+i] = one[i]\n            a = 0\n            b = 0\n            result.dat[h].build()\n    \n    proc initWaveletMatrix*(v:seq[int]):WaveletMatrix=\n        var x = v.max()\n        if x == 0:\n            return initWaveletMatrix(v,1)\n        return initWaveletMatrix(v,x.fastLog2()+1)\n    \n    proc get_child*(self:WaveletMatrix,h,l,r:int):tuple[l0,r0,l1,r1:int]=\n        # 高さh+1における[l,r)に該当する部分を見ているとする。\n        # その子に該当する部分を[l0,r0),[l1,r1)としたとき、(l0,r0,l1,r1)を返す。\n        var c0  = self.N - self.dat[h].rank(self.N)\n        result.l0 = l - self.dat[h].rank(l)\n        result.r0 = r - self.dat[h].rank(r)\n        result.l1 = self.dat[h].rank(l) + c0\n        result.r1 = self.dat[h].rank(r) + c0\n\n    \n    proc kth_smallest*(self:WaveletMatrix,l,r,k:int):int=\n        # [l,r) 内で、k番目に小さいものを出力\n        var k = k\n        var l = l\n        var r = r\n        for h in countdown(self.H-1,0,1):\n            var (l0,r0,l1,r1) = self.get_child(h,l,r)\n            if k < r0-l0:\n                l = l0\n                r = r0\n            else:\n                l = l1\n                r = r1\n                k -= r0-l0\n                result += 1 shl h\n    \n    proc range_lowerbound*(self:WaveletMatrix,l,r,x:int):int=\n        var x = x\n        var l = l\n        var r = r\n        var now = 0\n        for h in countdown(self.H-1,0,1):\n            var (l0,r0,l1,r1) = self.get_child(h,l,r)\n            if (now + 1 shl h) > x:\n                l = l0\n                r = r0\n            else:\n                l = l1\n                r = r1\n                now += 1 shl h\n                result += r0-l0\n    \n    proc range_upperbound*(self:WaveletMatrix,l,r,x:int):int=\n        var x = x\n        var l = l\n        var r = r\n        var now = 0\n        for h in countdown(self.H-1,0,1):\n            var (l0,r0,l1,r1) = self.get_child(h,l,r)\n            if (now + 1 shl h) >= x:\n                l = l0\n                r = r0\n            else:\n                l = l1\n                r = r1\n                now += 1 shl h\n                result += r0-l0\n        result += r-l"


#[

数直線上のN個の座標 X_1 , X_2 , ... , X_Nが与えられる。

以下のクエリがQ個与えられるので、順に処理してください。

l,rと座標xが与えられる。min(abs(X_i - x) i in l..r )を求めよ。


]#

var N = ii()
var X = lii(N)
var Q = ii()
var WM = X.initWaveletMatrix()

for _ in range(Q):
    var l,r = ii()
    l -= 1
    var x = ii()

    var res = INF

    var a = WM.range_upperbound(l,r,x)-1
    if a != -1:
        res.min = x-WM.kth_smallest(l,r,a)
    
    var b = WM.range_lowerbound(l,r,x)
    if b != r-l:
        res.min = WM.kth_smallest(l,r,b)-x
    
    echo res