Problem: Problem

Beans are popular at Otsu University. N beans are lined up in a straight line. Each is numbered from 0 to N-1, and the hardness of the i-th bean is ai.

Cyan considers the ideal bean hardness to be D. However, Cyan doesn't want to go get the beans that are too far away because he is troublesome. Therefore, Cyan wants to know the beans whose hardness is closest to D among the l-th to r-th beans.

Cyan asks Q questions, so create a program to find the minimum value of | bean hardness − D | in the closed interval [l, r] for each question. (However, | a | represents the absolute value of a.)

Constraints

The input satisfies the following constraints.

* 1 ≤ N ≤ 105
* 0 ≤ | ai | ≤ 106 (0 ≤ i ≤ N−1)
* 1 ≤ Q ≤ 105
* 0 ≤ Di ≤ 106
* 0 ≤ li ≤ ri ≤ N-1

Input

The input is given in the following format.


N
a0 a1 ... aN−1
Q
l0 r0 D0
l1 r1 D1
..
..
..
lQ−1 rQ−1 DQ−1


The first line is given one integer N. On the second line, N integers are given, separated by blanks. On the third line, the number of queries is given as one integer Q. The query values ​​l, r, and D are given in the following 4 to 3 + Q lines.

Output

For each query, output the absolute value of the difference between D and the hardness of the bean closest to hardness D among the [l, r] th beans on one line.

Examples

Input

3
1 2 3
3
0 2 2
0 2 4
0 0 2


Output

0
1
1


Input

10
4 5 0 21 9 100 12 9 0 8
5
0 3 20
2 5 100
8 9 9
5 5 10
0 9 20


Output

1
0
1
90
1

Solution (in CPP):

Solution:
   #include <bits/stdc++.h>

//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-10)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            

                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[1200010];
                int inv[1200010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }

                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
                
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
//    mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
      
       
       
                               //----------------kokomade tenpure------------

// verify
// CF 813E
// JAG夏2018 day3D
// yukicoder 738
struct BV{
	
	private:
	public:
	int N;
	vector<int> RAN;
	vector<int> SEL1;
	vector<int> SEL0;
	int k0=0,k1=0;
	vector<bool> VEC;
	void shoki1(int NN){
		
		N=NN;
		
		VEC.resize(N,false);
		RAN.resize(N+1,0);
		
		
	}
	void setbit(int i){
		VEC[i]=1;
	}
	void resetbit(int i){
		VEC[i]=0;
	}
	void shoki2(){
		for(int i=0;i<N;i++){
			if(VEC[i]){
				RAN[i]=k1;
				k1++;
			}
			else{
				RAN[i]=k0;
				k0++;
			}
		}
		SEL1.resize(k1);
		SEL0.resize(k0);
		k0=0,k1=0;
		for(int i=0;i<N;i++){
			if(VEC[i]){
				SEL1[k1]=i;
				k1++;
			}
			else{
				SEL0[k0]=i;
				k0++;
			}
		}
	}
	
	
	int rank(int it){ return RAN[it];}
	int rank0(int it){
		if(it==N) return k0;
		if(VEC[it])return it-RAN[it];
		else return RAN[it];
	}
	int rank1(int it){
		if(it==N) return k1;
		if(VEC[it]==0)return it-RAN[it];
		else return RAN[it];
	}
	int select(int ko,bool b){
		if(b){
			if(ko>=k1)return -1;
			else return SEL1[ko];
		}
		else{
			if(ko>=k0)return -1;
			else return SEL0[ko];
		}
	}
	int access(int it) {return VEC[it];}

};

struct wavlet_matrix{
	private:
	public:
	
	int N;
	
	vector<int> VEC;
	int d;
	
	vector<BV> bv;
	vector<int> zero;
	
	//vector<vector<int>> rui;
	
	void shoki1(vector<int> &input,int D){
		VEC=input;
		N=input.size();
		d=D;
		bv.resize(d);
		zero.resize(d);
		/*
		/////////////////////////////////////////////////////////////
		rui.resize(d);
		
		/////////////////////////////////////////////////////////////
		*/
	}
	void shoki2(){
		
		for(int i=d-1;i>=0;i--){
			
			bv[i].shoki1(N);
			vector<int> mae,ato;
			for(int j=0;j<N;j++){
			
				if(VEC[j]&(1ll<<i)){
					
					ato.pb(VEC[j]);
					bv[i].setbit(j);
				}
				else{
					mae.pb(VEC[j]);
				}
			}
			
			zero[i]=(int)mae.size();
			bv[i].shoki2();
			
			mae.insert(mae.end(),ato.begin(),ato.end());
			
			/*
			/////////////////////////////////////////////////////////////
			rui[i]=mae;
			for(int j=1;j<N;j++)rui[i][j]+=rui[i][j-1];
			/////////////////////////////////////////////////////////////
			*/
			
			
			swap(VEC,mae);
		}
		
	}
	
	
	int access(int r){
		int ans=0;
		for(int i=d-1;i>=0;i--){
			if(bv[i].access(r)){
				ans+=(1ll<<i);
				r=zero[i]+bv[i].rank(r);
			}
			else{
				r=bv[i].rank(r);
			}
		}
		
		return ans;
	}
	
	int range_rank(int val, int l,int r){ // [l,r) にあるvalの個数
		
		
		
		for(int i=d-1;i>=0;i--){
			if(val&(1ll<<i)){
				r=zero[i]+bv[i].rank1(r);
				l=zero[i]+bv[i].rank1(l);
			}
			else{
				r=bv[i].rank0(r);
				l=bv[i].rank0(l);
			}
			
			
			if(l>=r) return 0;
		}
	
	return r-l;
	}
	
	int rank(int val,int pos){// 0,1,...,pos にあるvalの個数
		return range_rank(val,0,pos+1);
	}
	
	int select(int val,int kth){// kth 番目の valの位置 無いなら-1
		
		
		int l=0,r=N;
		for(int i=d-1;i>=0;i--){
			if(val&(1ll<<i)){
				r=zero[i]+bv[i].rank1(r);
				l=zero[i]+bv[i].rank1(l);
			}
			else{
				r=bv[i].rank0(r);
				l=bv[i].rank0(l);
			}
			
			
			if(l+kth>=r) return -1;
		}
		int pos=l+kth;
		//cout<<" "<<pos<<" "<<endl;;
		for(int i=0;i<d;i++){
			if(val&(1ll<<(i))){
			
				pos=bv[i].select(pos-zero[i],1);
			}
			else{
				pos=bv[i].select(pos,0);
			}
	//		cout<<pos<<endl;
		}
		return pos;
		
	}
	
	int x_th_min(int x,int l,int r){
		//区間[l,r)で小さいほうからk番目の値
		// 0 <= x < r-l
		
		int ans=0;
		
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			int z=t2-t1;
		//	cout<<x<<" "<<l<<" "<<r<<" "<<ans<<endl;
			if(z>x){
				l=t1,r=t2;
			}
			else{
				ans+=(1ll<<i);
				x-=z;
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
		}
		return ans;
	}
	
	int range_min(int l,int r){
		return x_th_min(0,l,r);
	}
	
	int range_max(int l,int r){
		return x_th_min(r-l-1,l,r);
	}
	
	
	int range_count_prefix(int l,int r,int val){
		//区間[l,r)に存在する値が[0,val)な項の個数
		if(val<=0) return 0;
		if(l>=r)return 0;
		val--;
		//[0,val]に変更
		int ans=0;
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			
			if(val&(1ll<<i)){
				ans+=t2-t1;				
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1;
				r=t2;
			}
		}
		ans+=r-l;
		
		return ans;
		
	}
	
	int range_count(int l,int r,int vl,int vr){
		//区間[l,r)に存在する値が[vl,vr)な項の個数
		return range_count_prefix(l,r,vr)-range_count_prefix(l,r,vl);
		
	}		
	
	
	int range_bound_max(int l,int r,int val){
		//区間[l,r)に存在する値がval以下の中で最大の値
		
		if(l>=r) return -1;
		
		int dep=-1;
		int cl=-1;
		int cr=-1;
		int cur=0;
		
		int ima=0;
		for(int i=d-1;i>=0;i--){
			
			if(i==0){
				if(val&1){
					if(l<r){
						dep=0;
						cl=l,cr=r;
						cur=ima;
					}
				}
				else{
					int t1=bv[i].rank0(l);
					int t2=bv[i].rank0(r);
					if(t1<t2) return ima;
				}
				break;
				
			}
			
			if(val&(1ll<<i)){
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				if(t1!=t2){
					dep=i-1;
					cl=t1,cr=t2;
					cur=ima;
				}
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
				ima+=(1ll<<i);
			}
			else{
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				l=t1,r=t2;
				
			}
		}
		if(dep==-1) return -1;
		ima=cur;
		l=cl,r=cr;
		for(int i=dep;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			if(r-l>t2-t1){
				ima+=(1ll<<i);
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1,r=t2;
			}
		}
		
		return ima;
	}
	
	
	int range_bound_min(int l,int r,int val){
		//区間[l,r)に存在する値がval以上の中で最小の値
		
		if(l>=r) return -1;
		
		int dep=-1;
		int cl=-1;
		int cr=-1;
		int cur=0;
		
		int ima=0;
		for(int i=d-1;i>=0;i--){
			
			if(i==0){
				if((val&1)==0){
					if(l<r){
						dep=0;
						cl=l,cr=r;
						cur=ima;
					}
				}
				else{
					int t1=zero[i]+l-bv[i].rank0(l);
					int t2=zero[i]+r-bv[i].rank0(r);
					ima+=(1ll<<i);
					if(t1<t2) return ima;
				}
				break;
				
			}
			
			if((val&(1ll<<i))==0){
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				int s1=zero[i]+l-t1;
				int s2=zero[i]+r-t2;
				if(s1<s2){
					dep=i-1;
					cl=s1,cr=s2;
					cur=ima+(1ll<<i);
				}
				l=t1,r=t2;
			}
			else{
				int t1=bv[i].rank0(l);
				int t2=bv[i].rank0(r);
				int s1=zero[i]+l-t1;
				int s2=zero[i]+r-t2;
				l=s1,r=s2;
				ima=ima+(1ll<<i);
				
			}
		}
	
		if(dep==-1) return -1;
		ima=cur;
		l=cl,r=cr;
		
		for(int i=dep;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			if(t2-t1==0){
				ima+=(1ll<<i);
				l=zero[i]+l-t1;
				r=zero[i]+r-t2;
			}
			else{
				l=t1,r=t2;
			}
			assert(l<r);
		}
		
		return ima;
	}
	
	
	/*
	int range_sum_prefix(int l,int r,int val){
		//区間[l,r)に存在する値が[0,val)な項の和
		if(val<=0) return 0;
		if(l>=r)return 0;
		val--;
		//[0,val]に変更
		int ans=0;
		
		for(int i=d-1;i>=0;i--){
			int t1=bv[i].rank0(l);
			int t2=bv[i].rank0(r);
			
			if(val&(1ll<<i)){
				ans+=(t2>0?rui[i][t2-1]:0)-(t1>0?rui[i][t1-1]:0);
				
				l=zero[i]+l-t1;;
				r=zero[i]+r-t2;
			}
			else{
				l=t1;
				r=t2;
			}
			
		}
		
		ans-=(l>0?rui[0][l-1]:0)-(r>0?rui[0][r-1]:0);
		
		return ans;
		
	}
	
	int range_sum(int l,int r,int vl,int vr){
		//区間[l,r)に存在する値が[vl,vr)な項の和
		return range_sum_prefix(l,r,vr)-range_sum_prefix(l,r,vl);
		
	}
	*/
};




 signed main(){
 	

    	       cin.tie(0);
   			ios::sync_with_stdio(false);

 	int n;
 	cin>>n;
 	vector<int>ve(n);
 	for(int i=0;i<n;i++)cin>>ve[i];
 		wavlet_matrix wt;
 	wt.shoki1(ve,22);
 	wt.shoki2();
 	
 	
 	int q;
 	cin>>q;
 	for(int i=0;i<q;i++){
 		int l,r,d;
 		cin>>l>>r>>d;
 		r++;
 		int ans=inf*10000ll;
 		int v1=wt.range_bound_min(l,r,d);
 		if(v1!=-1)ans=min(ans,v1-d);
 		int v2=wt.range_bound_max(l,r,d);
 		if(v2!=-1)ans=min(ans,d-v2);
 		
 		cout<<ans<<endl;
 	}
 	
 
 	return 0;

  }