package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"

	"reflect"
)

var wg = bufio.NewScanner(os.Stdin)

const (
	inf            = int(1e18)
	initialBufSize = int(1e6)
	maxBufSize     = int(1e6)
)

var buf []byte = make([]byte, initialBufSize)

//区間最小をとるモノイド
type min_monoid int

func (x min_monoid) Get() interface{} {
	return x
}
func (x min_monoid) Op(y Monoid) Monoid {
	if int(y.(min_monoid)) < int(x) {
		return y
	} else {
		return x
	}
}
func (x min_monoid) Ide() Monoid {
	return min_monoid(inf)
}

//区間最大をとるモノイド
type max_monoid int

func (x max_monoid) Get() interface{} {
	return x
}

func (x max_monoid) Op(y Monoid) Monoid {
	if int(y.(max_monoid)) > int(x) {
		return y
	} else {
		return x
	}
}
func (x max_monoid) Ide() Monoid {
	return max_monoid(-inf)
}

func main() {
	n := nextInt()
	X := make([]struct{ val, idx int }, n)
	for i := 0; i < n; i++ {
		X[i].val = nextInt()
		X[i].idx = i
	}
	q := nextInt()
	Q := make([]struct{ l, r, val, idx int }, q)
	for i := 0; i < q; i++ {
		Q[i].l = nextInt() - 1
		Q[i].r = nextInt()
		Q[i].val = nextInt()
		Q[i].idx = i
	}

	ans := make([]int, q)
	for i := 0; i < q; i++ {
		ans[i] = inf
	}
	//step 1. min_monoid
	sort.Slice(Q, func(i, j int) bool {
		return Q[i].val > Q[j].val
	})
	sort.Slice(X, func(i, j int) bool {
		return X[i].val > X[j].val
	})
	seg, _ := Gen(min_monoid(0), n)
	for itr, i := 0, 0; i < q; i++ {
		for itr < n && X[itr].val >= Q[i].val {
			seg.Set(X[itr].idx, min_monoid(X[itr].val))
			itr++
		}
		val := seg.Prod(Q[i].l, Q[i].r).(min_monoid)
		ans[Q[i].idx] = min(ans[Q[i].idx], int(val)-Q[i].val)
	}

	//step 2.max_monoid
	sort.Slice(Q, func(i, j int) bool {
		return Q[i].val < Q[j].val
	})
	sort.Slice(X, func(i, j int) bool {
		return X[i].val < X[j].val
	})
	seg1, _ := Gen(max_monoid(0), n)
	for itr, i := 0, 0; i < q; i++ {
		for itr < n && X[itr].val < Q[i].val {
			seg1.Set(X[itr].idx, max_monoid(X[itr].val))
			itr++
		}
		val := seg1.Prod(Q[i].l, Q[i].r).(max_monoid)
		ans[Q[i].idx] = min(ans[Q[i].idx], Q[i].val-int(val))
	}
	//step 3.get answer
	for _, v := range ans {
		fmt.Printf("%d\n", v)
	}
}

/*
Monoid-Structure should be decleared some-where else.
-> op(Monoid,Monoid)Monoid & ide()Monoid is required.
*/

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

type Monoid interface {
	Get() interface{}
	Op(Monoid) Monoid
	Ide() Monoid
}

type SegTree struct {
	monoid_type Monoid
	op          func(Monoid) Monoid /* op */
	e           func() Monoid       /*identity*/
	d           []Monoid
	_d          []Monoid
	n           int /* size*/
	log         int
	size        int
}

func Gen(monoid Monoid, n int) (SegTree, bool) {

	seg := SegTree{monoid_type: monoid, op: monoid.Op, e: monoid.Ide, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0}
	collect := true

	switch n > 0 {
	case true:
		seg.d = make([]Monoid, n)
		for i := range seg.d {
			seg.d[i] = seg.e()
		}
	default:
		collect = false
		return seg, collect
	}

	seg.n = len(seg.d)
	for ord := 0; (1 << ord) < seg.n; {
		ord++
		seg.log = ord
	}

	seg.size = 1 << seg.log
	seg._d = make([]Monoid, 2*seg.size)
	for i := range seg._d {
		seg._d[i] = seg.e()
	}

	for i := 0; i < seg.n; i++ {
		seg._d[seg.size+i] = seg.d[i]
	}
	for i := seg.size - 1; i > 0; i-- {
		seg._update(i)
	}
	return seg, collect
}

func SliceGen(seg SegTree, array []Monoid) bool {
	ok := true
	if len(array) != seg.n {
		ok = false
		return ok
	}

	for _, v := range array {
		if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {
			ok = false
			return ok
		}
	}

	for i, v := range array {
		seg.Set(i, v)
	}

	for i := seg.size - 1; i > 0; i-- {
		seg._update(i)
	}

	return ok
}

func (seg SegTree) _update(k int) {
	seg._d[k] = seg._d[2*k].Op(seg._d[2*k+1])
}

func (seg SegTree) Set(p int, x Monoid) {
	//a[p] -> x
	p += seg.size
	seg._d[p] = x
	for i := 1; i <= seg.log; i++ {
		seg._update(p >> i)
	}
}

func (seg SegTree) Get(p int) Monoid {
	// a[p]
	return seg._d[p+seg.size]
}

func (seg SegTree) OverWrite(p int, f func(Monoid) Monoid) {
	p += seg.size
	m := seg._d[p]
	seg._d[p] = f(m)
	for i := 1; i <= seg.log; i++ {
		seg._update(p >> i)
	}
}

func (seg SegTree) Prod(l, r int) Monoid {
	//op(a[l..r))
	sml := seg.e()
	smr := seg.e()
	l += seg.size
	r += seg.size
	for l < r {
		if l&1 == 1 {
			sml = sml.Op(seg._d[l])
			l++
		}
		if r&1 == 1 {
			r--
			smr = seg._d[r].Op(smr)
		}
		l >>= 1
		r >>= 1
	}
	return sml.Op(smr)
}

func (seg SegTree) AllProd() Monoid {
	return seg._d[1]
}

func (seg SegTree) MaxRight(left int, f func(Monoid) bool) int {
	if left == seg.n {
		return seg.n
	}
	left += seg.size
	sm := seg.e()
	first := true

	for first || (left&(-left)) != left {
		first = false
		for left&1 == 0 {
			left >>= 1
		}
		if !f(sm.Op(seg._d[left])) {
			for left < seg.size {
				left <<= 1
				if f(sm.Op(seg._d[left])) {
					sm = sm.Op(seg._d[left])
					left++
				}
			}
			return left - seg.size
		}
		sm = sm.Op(seg._d[left])
		left++
	}
	return seg.n
}

func (seg SegTree) MinLeft(right int, f func(Monoid) bool) int {
	if right == 0 {
		return 0
	}
	right += seg.size
	sm := seg.e()
	first := true

	for first || (right&(-right)) != right {
		first = false
		right--
		for right > 1 && right&1 == 0 {
			right >>= 1
		}
		if !f(sm.Op(seg._d[right])) {
			for right < seg.size {
				right = right*2 + 1
				if f(sm.Op(seg._d[right])) {
					sm = sm.Op((seg._d[right]))
					right--
				}
			}
			return right + 1 - seg.size
		}
		sm = sm.Op(seg._d[right])
	}
	return 0
}

func init() {
	wg.Split(bufio.ScanWords)
	wg.Buffer(buf, maxBufSize)
}

func nextInt() int {
	wg.Scan()
	i, e := strconv.Atoi(wg.Text())
	if e != nil {
		panic(e)
	}
	return i
}