#include <bits/stdc++.h>
using namespace std;


template <class F> class y_combinator {
    F f;

   public:
    y_combinator(F&& f) : f(std::forward<F>(f)) {}
    template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); }
};

constexpr int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T, class U = std::less<T>> using prique = priority_queue<T, vector<T>, U>;

#define overload(a, b, c, d, e, ...) e
#define len(x) (ll)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep1(n) for (ll _ = 0; _ < ll(n); _++)
#define rep2(i, n) for (ll i = 0; i < ll(n); i++)
#define rep3(i, a, b) for (ll i = ll(a); i < ll(b); i++)
#define rep4(i, a, b, c) for (ll i = ll(a); i < ll(b); i += ll(c))
#define rep(...) overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; i--)

template <class T> void dedup(vector<T>& a) { sort(all(a)), a.erase(unique(all(a)), a.end()); }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }

namespace cppio {

template <typename T> struct is_tuple_like : false_type {};
template <typename... Ts> struct is_tuple_like<tuple<Ts...>> : true_type {};
template <typename T, typename U> struct is_tuple_like<pair<T, U>> : true_type {};

template <typename T, typename = void> struct is_container : false_type {};
template <typename T> struct is_container<T, void_t<decltype(begin(declval<T&>()))>> : bool_constant<!is_same_v<decay_t<T>, string> && !is_same_v<decay_t<T>, char*> && !is_same_v<decay_t<T>, const char*> && !is_array_v<remove_reference_t<T>>> {};

template <typename T> void _in(T& x) {
    if constexpr (is_tuple_like<T>::value) apply([](auto&... elems) { (_in(elems), ...); }, x);
    else if constexpr (is_container<T>::value) {
        for (auto& e : x) _in(e);
    } else cin >> x;
}

template <typename... Ts> void _in_all(Ts&... args) { (_in(args), ...); }

template <typename T> void _out(const T& x) {
    bool first = true;
    if constexpr (is_tuple_like<T>::value) {
        apply([&](const auto&... elems) { ((cout << (first ? "" : " "), _out(elems), first = false), ...); }, x);
    } else if constexpr (is_container<T>::value) {
        for (const auto& e : x) {
            if (!first) cout << ' ';
            _out(e), first = false;
        }
    } else cout << x;
}

template <typename... Ts> void _print(const Ts&... args) {
    bool first = true;
    ((cout << (first ? "" : " "), _out(args), first = false), ...);
}

template <typename... Ts> void _out_all(const Ts&... args) { _print(args...), cout << '\n'; }
template <typename... Ts> void _out_no_el(const Ts&... args) { _print(args...); }

}  // namespace cppio

#define IN(...) cppio::_in_all(__VA_ARGS__)
#define OUT(...) cppio::_out_all(__VA_ARGS__)
#define out(...) cppio::_out_no_el(__VA_ARGS__)

#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...)  ll __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); IN(name)
#define VV(type, name, h, w)  vector<vector<type>> name(h, vector<type>(w)); IN(name)
#define RETURN(...) do { __VA_ARGS__; return; } while (0)

bool Yes(bool b = true) { OUT(b ? "Yes" : "No"); return b; }
bool No(bool b = true) { Yes(!b); return b; }
bool YES(bool b = true) { OUT(b ? "YES" : "NO"); return b; }
bool NO(bool b = true) { YES(!b); return b; }

#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#endif

template <class T> struct Compress {
   private:
    std::vector<T> vs;
    bool built = false;

   public:
    Compress() = default;
    explicit Compress(const std::vector<T>& vs) : vs(vs) {}
    template <class InputIterator> Compress(InputIterator first, InputIterator last) : vs(first, last) {}

    void reserve(size_t n) { vs.reserve(n); }

    template <class... Ts> void add(const Ts&... xs) {
        (vs.push_back(xs), ...);
        built = false;
    }

    void build() {
        std::sort(vs.begin(), vs.end());
        vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
        built = true;
    }

    int rank(const T& x) const {
        assert(built);
        return (int)(lower_bound(vs.begin(), vs.end(), x) - vs.begin());
    }

    const T& operator[](size_t i) const {
        assert(built && i < vs.size());
        return vs[i];
    }

    bool exists(const T& x) const {
        assert(built);
        size_t i = this->rank(x);
        return i < this->size() && this->operator[](i) == x;
    }

    size_t size() const {
        assert(built);
        return vs.size();
    }

    static std::vector<int> compressed(const std::vector<T>& vs) {
        Compress<T> cp(vs);
        cp.build();
        std::vector<int> res;
        res.reserve(vs.size());
        for (const auto& x : vs) res.push_back(cp.rank(x));
        return res;
    }
};

struct BitVector {
   private:
    int n, b;
    bool built = false;
    vector<u64> bit, sum;

   public:
    explicit BitVector(int n) : n(n) {
        b = (n >> 6) + 1;
        bit.resize(b);
        sum.resize(b + 1);
    }
    void set(int i) { bit[i >> 6] |= 1ULL << (i & 63), built = false; }
    void flip(int i) { bit[i >> 6] ^= 1ULL << (i & 63), built = false; }
    bool get(int i) const { return bit[i >> 6] >> (i & 63) & 1; }
    bool operator[](int i) const { return get(i); }
    void build() {
        built = true;
        for (int i = 0; i < b; i++) sum[i + 1] = sum[i] + std::popcount(bit[i]);
    }
    int rank(int i) const {
        assert(built);
        return sum[i >> 6] + std::popcount(bit[i >> 6] & ((1ULL << (i & 63)) - 1));
    }
    int rank(bool x, int i) const { return x ? rank(i) : i - rank(i); }
    int rank(bool x, int l, int r) const { return rank(x, r) - rank(x, l); }
};

template <class T> struct WaveletMatrix {
   private:
    const int LOG = 25;
    int N;
    vector<BitVector> bitvector;
    vector<int> mid;
    Compress<T> cp;
    void build(vector<T> v) {
        cp = Compress<T>(v);
        cp.build();
        for (auto& e : v) e = cp.rank(e);
        N = v.size();
        bitvector.assign(LOG, BitVector(N));
        mid.resize(LOG);
        vector<T> v0(N), v1(N);
        for (int it = LOG - 1; it >= 0; it--) {
            int l = 0, r = 0;
            for (int i = 0; i < N; i++) {
                if (v[i] >> it & 1) {
                    v1[r++] = v[i];
                    bitvector[it].set(i);
                } else {
                    v0[l++] = v[i];
                }
            }
            bitvector[it].build();
            mid[it] = l;
            v.swap(v0);
            for (int i = 0; i < r; i++) v[i + l] = v1[i];
        }
    }

   public:
    explicit WaveletMatrix(const vector<T>& v) { build(v); }
    T access(int p) const {
        assert(0 <= p && p < N);
        int res = 0;
        for (int i = LOG - 1; i >= 0; i--) {
            if (bitvector[i].get(p)) {
                p = bitvector[i].rank(true, p) + mid[i];
                res |= 1 << i;
            } else {
                p = bitvector[i].rank(false, p);
            }
        }
        return cp[res];
    }
    int count(int l, int r, const T& x) const {
        assert(0 <= l && l <= r && r <= N);
        if (!cp.exists(x)) return 0;
        int v = cp.rank(x);
        for (int it = LOG - 1; it >= 0; it--) {
            if (v >> it & 1) {
                l = mid[it] + bitvector[it].rank(true, l);
                r = mid[it] + bitvector[it].rank(true, r);
            } else {
                l = bitvector[it].rank(false, l);
                r = bitvector[it].rank(false, r);
            }
        }
        return r - l;
    }
    T kth_smallest(int l, int r, int k) const {
        assert(0 <= l && l <= r && r <= N);
        assert(0 <= k && k < r - l);
        int res = 0;
        for (int it = LOG - 1; it >= 0; it--) {
            int cnt0 = bitvector[it].rank(false, l, r);
            if (k < cnt0) {
                l = bitvector[it].rank(false, l);
                r = bitvector[it].rank(false, r);
            } else {
                l = mid[it] + bitvector[it].rank(true, l);
                r = mid[it] + bitvector[it].rank(true, r);
                res |= 1 << it;
                k -= cnt0;
            }
        }
        return cp[res];
    }
    T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - 1 - k); }
    int range_freq(int l, int r, const T& upper) const {
        assert(0 <= l && l <= r && r <= N);
        int v = cp.rank(upper);
        int res = 0;
        for (int it = LOG - 1; it >= 0; it--) {
            if (v >> it & 1) {
                res += bitvector[it].rank(false, l, r);
                l = mid[it] + bitvector[it].rank(true, l);
                r = mid[it] + bitvector[it].rank(true, r);
            } else {
                l = bitvector[it].rank(false, l);
                r = bitvector[it].rank(false, r);
            }
        }
        return res;
    }
    int range_freq(int l, int r, const T& lower, const T& upper) const { return range_freq(l, r, upper) - range_freq(l, r, lower); }
};

void run_case() {
    INT(N);
    VEC(int, A, N);
    WaveletMatrix<int> wm(A);
    INT(Q);
    while (Q--) {
        INT(l, r, x);
        l--;
        ll ans = 1e18;
        if (wm.count(l, r, x)) ans = 0;
        {
            int cnt = wm.range_freq(l, r, x);
            if (cnt != 0) {
                chmin<ll>(ans, x-wm.kth_smallest(l, r, cnt - 1));
            }
            if (cnt != r - l) {
                chmin<ll>(ans, wm.kth_smallest(l, r, cnt) - x);
            }
        }
        OUT(ans);
    }
}
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::fixed(std::cout).precision(16);
    ll t = 1;
    while (t--) run_case();
}