//@formatter:off #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define rrep(i,n) for (int i = int(n)-1; i >= 0; i--) #define rep2(i,s,n) for (int i = int(s); i < int(n); ++i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define vi vector #define vvi vector> #define vl vector #define vvl vector> #define vd vector #define vvd vector> #define vs vector #define vc vector #define vvc vector> #define vb vector #define vvb vector> #define vp vector

#define vvp vector> using namespace std; using ll = long long; using P = pair; using LP = pair; template istream& operator>>(istream &is,pair &p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream &os,const pair &p) { return os<<'{'< istream& operator>>(istream &is,vector &v) { for(T &t:v){is>>t;} return is; } template ostream& operator<<(ostream &os,const vector &v) { os<<'[';rep(i,v.size())os< bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;} template bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;} const int inf = 1001001001; const ll linf = 1001001001001001001; //@formatter:on int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vi X(n); cin >> X; int q; cin >> q; vi l(q), r(q), x(q); rep(i, q) { cin >> l[i] >> r[i] >> x[i]; l[i]--; } vi ord(q); iota(all(ord), 0); int d = (int)sqrt(n) + 1; auto cmp = [&](int i, int j) { if (l[i] / d != l[j] / d) return l[i] / d < l[j] / d; return r[i] < r[j]; }; sort(all(ord), cmp); multiset st; auto add = [&](int i) { st.insert(X[i]); }; auto erase = [&](int i) { st.erase(st.find(X[i])); }; int nl = 0, nr = 0; vi ans(q, inf); rep(i, q) { int now = ord[i]; while (nr < r[now]) add(nr++); while (nl > l[now]) add(--nl); while (nr > r[now]) erase(--nr); while (nl < l[now]) erase(nl++); auto it = st.lower_bound(x[now]); if (it != st.end()) chmin(ans[now], *it - x[now]); if (it != st.begin()) { it--; chmin(ans[now], x[now] - *it); } } for (int i : ans) cout << i << '\n'; }