#include using namespace std; #define rep(i,n) for(ll i=0;i=0;i--) #define perl(i,r,l) for(ll i=r-1;i>=l;i--) #define fi first #define se second #define pb push_back #define ins insert #define pqueue(x) priority_queue,greater> #define all(x) (x).begin(),(x).end() #define CST(x) cout<; using vvl=vector>; using pl=pair; using vpl=vector; using vvpl=vector; const ll MOD=1000000007; const ll MOD9=998244353; const int inf=1e9+10; const ll INF=4e18; const ll dy[8]={-1,0,1,0,1,1,-1,-1}; const ll dx[8]={0,-1,0,1,1,-1,1,-1}; template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } ll near(vl v,ll t){ if(v.empty())return INF; auto p=lower_bound(all(v),t); ll ret=INF; if(p!=v.end()){ chmin(ret,abs(t-*p)); } if(p!=v.begin()){ p--; chmin(ret,abs(t-*p)); } return ret; } int main(){ ll n;cin >> n;ll m=1000; vl X(m*m,INF);rep(i,n)cin >> X[i]; vvl b(m); rep(i,X.size()){ b[i/m].pb(X[i]); } rep(i,m)sort(all(b[i])); ll q;cin >> q; while(q--){ ll x,y,t;cin >>x >> y >> t;x--; ll ans=INF; for (ll k = 0; k < m; ++k) { ll l = k * m, r = (k + 1) * m; if (r <= x || y <= l) continue; if (x <= l && r <= y) { chmin(ans,near(b[k],t)); } else { for (int i = max(x, l); i < min(y, r); ++i) { chmin(ans,abs(t-X[i])); } } } cout << ans <