#include using namespace std; const int INF = 1000000000; template struct binary_indexed_tree{ int N; vector BIT; binary_indexed_tree(int n){ N = 1; while (N < n){ N *= 2; } BIT = vector(N + 1, 0); } void add(int i, T x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } T sum(int L, int R){ return sum(R) - sum(L); } T all(){ return BIT[N]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector X(N); for (int i = 0; i < N; i++){ cin >> X[i]; } vector X2 = X; sort(X2.begin(), X2.end()); int Q; cin >> Q; vector l(Q), r(Q), x(Q); for (int i = 0; i < Q; i++){ cin >> l[i] >> r[i] >> x[i]; l[i]--; } vector tv(Q, INF), fv(Q, -1); while (true){ vector mid(Q, -1); bool update = false; for (int i = 0; i < Q; i++){ if (tv[i] - fv[i] > 1){ mid[i] = (tv[i] + fv[i] + 2) / 2 - 1; update = true; } } if (!update){ break; } vector> padd(N); for (int i = 0; i < N; i++){ int p = lower_bound(X2.begin(), X2.end(), X[i]) - X2.begin(); padd[i].push_back(p); } vector>> add(N); vector>> sub(N); for (int i = 0; i < Q; i++){ if (mid[i] != -1){ int L = x[i] - mid[i]; int R = x[i] + mid[i]; int Lp = lower_bound(X2.begin(), X2.end(), L) - X2.begin(); int Rp = upper_bound(X2.begin(), X2.end(), R) - X2.begin(); if (l[i] > 0){ sub[l[i] - 1].push_back(make_tuple(Lp, Rp, i)); } add[r[i] - 1].push_back(make_tuple(Lp, Rp, i)); } } binary_indexed_tree BIT(N); vector cnt(Q, 0); for (int i = 0; i < N; i++){ for (int j : padd[i]){ BIT.add(j, 1); } int addcnt = add[i].size(); for (int j = 0; j < addcnt; j++){ int L = get<0>(add[i][j]); int R = get<1>(add[i][j]); int id = get<2>(add[i][j]); cnt[id] += BIT.sum(L, R); } int subcnt = sub[i].size(); for (int j = 0; j < subcnt; j++){ int L = get<0>(sub[i][j]); int R = get<1>(sub[i][j]); int id = get<2>(sub[i][j]); cnt[id] -= BIT.sum(L, R); } } for (int i = 0; i < Q; i++){ if (mid[i] != -1){ if (cnt[i] == 0){ fv[i] = mid[i]; } else { tv[i] = mid[i]; } } } assert(false); } for (int i = 0; i < Q; i++){ cout << tv[i] << "\n"; } }