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

const int MAX_N = 1 << 17;
template<typename T, T INF>
struct Wavelet{
	void init(const vector<T>& A){
		N = 1;
		while(N < A.size()) N *= 2;
		for(int i = 0; i < N; i++){
			if(i < A.size()) sorted[i] = b[0][i] = A[i];
			else sorted[i] = b[0][i] = INF;
		}
		sort(sorted, sorted + N);
		for(int len = N, d = 0; len >= 1; len /= 2, d++){
			int g = 0;
			for(int l = 0; l < N; l += len){
				calc(l, l + len, d);
				for(int i = l; i < l + len; i++){
					group[d][i] = g;
					if(i != l) Left[d][i] += Left[d][i - 1];
				}
				g++;
			}
		}
	}
	// [l,r)????????????????????¨??????k??????(1-indexed)??????
	T  kth_element(int l, int r, int k){
		return kth_element(l, r, k, 0, N, 0);
	}
	/*
	[l,r)????????????????????¨???x????????????(1-index)?????\??????.
	x???2?????\???????????¨??????,??????????????????rank?????????.
	x???????????¨??????x????????§?????§????????????rank?????????.
	x?????????????????¨??????0?????????.
	*/
	int pos(int l, int r, T x){
		return pos(l, r, x, 0, N, 0);
	}
	// [l,r)???x?????°
	int freq(int l, int r, T x){
		return pos(l, r, x) - pos(l, r, x - 1);
	}
	// [l,r)???lx??\???rx??\????????°(?)
	int freq2(int l, int r, T lx, T rx){
		return pos(l, r, rx) - pos(l, r, lx - 1);
	}
private:
	int N;
	T sorted[MAX_N];
	T b[20][MAX_N];
	int Left[20][MAX_N];
	int group[20][MAX_N];

	int getLeftNum(int l, int r, int d){
		if(r <= l) return 0;
		int ret = Left[d][r - 1];
		if(l && group[d][l - 1] == group[d][r - 1]) ret -= Left[d][l - 1];
		return ret;
	}

	void calc(int l, int r, int d){
		int c = (l + r) / 2, len = r - l;
		multiset<T> lset(sorted + l, sorted + l + len / 2);
		int L = l, R = c;
		for(int i = l; i < r; i++){
			int val = b[d][i];
			if(lset.count(val)){
				b[d + 1][L] = val;
				L++;
				Left[d][i] = 1;
				lset.erase(lset.find(val));
			}
			else{
				b[d + 1][R] = val;
				R++;
				Left[d + 1][i] = 0;
			}
		}
	}
	// ??±??????d??§[L,R)?????¨?????????????????¨??????[l,r)???k??????(1-indexed)??????
	T kth_element(int l, int r, int k, int L, int R, int d){
		if(R - L == 1) return b[d][L];
		int len = r - l, mid = (L + R) / 2;
		// [l,r)????????§???????????????????????°
		int leftNum = getLeftNum(l, r, d), rightNum = len - leftNum;
		// ???????????????????????°???k??\????????????????????°???????????§???????????????????????°
		if(k <= leftNum){
			int newl = max(L, L + getLeftNum(L, l, d));
			int newr = min(mid, newl + leftNum);
			return kth_element(newl, newr, k, L, mid, d + 1);
		}
		else{
			int newl = max(mid, mid + (l - L - getLeftNum(L, l, d)));
			int newr = min(R, newl + rightNum);
			return kth_element(newl, newr, k - leftNum, mid, R, d + 1);
		}
	}
	int pos(int l, int r, T x, int L, int R, int d){
		if(R - L == 1){
			return l + 1 == r && sorted[l] <= x;
		}
		int mid = (L + R) / 2, len = r - l;
		int leftNum = getLeftNum(l, r, d), rightNum = len - leftNum;
		if(x < sorted[mid]){
			int newl = max(L, L + getLeftNum(L, l, d));
			int newr = min(mid, newl + leftNum);
			return pos(newl, newr, x, L, mid, d + 1);
		}
		else{
			int newl = max(mid, mid + (l - L - getLeftNum(L, l, d)));
			int newr = min(R, newl + rightNum);
			return leftNum + pos(newl, newr, x, mid, R, d + 1);
		}
	}
};

Wavelet<ll, 1LL << 50> W;

int main(){
	int N;
	scanf("%d", &N);
	vector<ll> a(N);
	for(int i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}

	W.init(a);
	int Q;
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++){
		int l, r, D;
		scanf("%d%d%d", &l, &r, &D);
		r++;
		int len = r - l;
		int ng = -1, ok = 1e6 + 1;
		while(abs(ng - ok) > 1){
			int mid = (ng + ok) / 2;
			int lx = D - mid, rx = D + mid;
			if(W.freq2(l, r, lx, rx) >= 1) ok = mid;
			else ng = mid;
		}
		printf("%d\n", ok);
	}
}


Measured memory_bytes: 45976