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<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<queue>
#include<cmath>
#include<functional>
#include<algorithm>
#define INF (1<<29)
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

inline int popCount(unsigned int x) {
	x = x - (( x >> 1 ) & 0x55555555);
	x = (x & 0x33333333) + (( x >> 2) & 0x33333333);
	x = ( x + ( x >> 4 )) & 0x0F0F0F0F;
	x = x + ( x >> 8 );
	x = x + ( x >> 16 );
	return x & 0x0000003F;
}


class BitVector{
	int n;
	int blocks;
	vector<unsigned int> B;
	vector<int> r;
public:
	BitVector(){}
	BitVector(int size){
		init(size);
	}
	void init(int size){
		n = size;
		blocks = (n>>5)+1;
		B.assign(blocks ,0);
		r.assign(blocks ,0);
	}
	void set(int k){
		B[k>>5] |= 1<<(k&31);
	}
	void build(){
		r[0]=0;
		for(int i=1;i<blocks;i++){
			r[i] = popCount(B[i-1]) + r[i-1];
		}
	}	
	bool access(int k)const{
		return B[k>>5] & 1<<(k&31);
	}
	//[0,k)の1の個数
	int rank(int k)const{
		return r[k>>5] + popCount(B[k>>5] & ((1<<(k&31))-1));
	}
};


//ウェーブレット行列
class WaveletMatrix{
	typedef int Val;
	static const Val NIL=-1;
	static const int BITLEN = 20;
	int len;
	BitVector bv[BITLEN];
	int encode(Val c)const{
		return c;
	}
	Val decode(int n)const{
		return n;
	}
	struct Node{
		int height,s,e,code;
		Node(){}
		Node(int a,int b,int c,int d):height(a),s(b),e(c),code(d){};
		bool operator <(Node a)const{return e-s<a.e-a.s;}
	};
public:
	int length()const{
		return len;
	}
	WaveletMatrix(){
	}
	template<class T>
	WaveletMatrix(const T &v){
		init(v);
	}
	template<class T>
	void init(const T &v){
		len = v.size();
		for(int i=0;i<BITLEN;i++){
			bv[i].init(v.size());
		}
		int *bucket;
		bucket = new int[2*len];
		int *cur,*next;
		cur = bucket;
		next = bucket+len;
		int rank0[BITLEN]={0};
		for(int i=0;i<len;i++){
			int n = encode(v[i]);
			cur[i] = n;
			for(int j=BITLEN-1;j>=0;j--){
				if((n&1<<j)==0)rank0[j]++;
			}
		}
		for(int i=BITLEN-1;;i--){
			for(int j=0;j<len;j++){
				if(cur[j]&1<<i)bv[i].set(j);
			}
			bv[i].build();
			if(i==0)break;
			int idx0=0,idx1=rank0[i];
			for(int j=0;j<len;j++){
				if(cur[j]&1<<i)next[idx1++]=cur[j];
				else next[idx0++]=cur[j];
			}
			swap(cur,next);
		}
		delete[] bucket;
	}
	int rank(int s,int e,Val c)const{
		int n = encode(c);
		for(int i=BITLEN-1;i>=0;i--){
			int ssum = bv[i].rank(s);
			int esum = bv[i].rank(e);
			if(n&1<<i){
				s = len-bv[i].rank(len) + ssum;
				e = s + esum-ssum;
			}else{
				s = s-ssum;
				e = e-esum;
			}
		}
		return e-s;
	}
	Val nextvalue(int s,int e,Val x,Val y)const{
		int lb = encode(x);
		int ub = encode(y)-1;
		Node a(-1,-1,-1,-1);
		for(int i=BITLEN-1;i>=0;i--){
			int ssum = bv[i].rank(s);
			int esum = bv[i].rank(e);
			int num1 = esum-ssum;
			if(lb&1<<i){
				s = len-bv[i].rank(len) + ssum;
				e = s + esum-ssum;
			}else{
				if(num1){
					int s1 = len-bv[i].rank(len) + ssum;
					int e1 = s1 + esum-ssum;
					a = Node(i-1,s1,e1,lb&~((1<<i)-1)|1<<i);
				}
				s = s-ssum;
				e = e-esum;
			}
			if(s==e)break;
			if(i==0)return decode(lb);
		}
		if(a.code==-1)return NIL;
		for(;a.height>=0;a.height--){
			int ssum = bv[a.height].rank(a.s);
			int esum = bv[a.height].rank(a.e);
			int num1 = esum-ssum;
			int num0 = a.e-a.s-num1;
			int s0 = a.s-ssum;
			int s1 = len-bv[a.height].rank(len) + ssum;
			if(num0){
				a.s=s0;
				a.e=s0+num0;
			}else{
				a.s=s1;
				a.e=s1+num1;
				a.code|=1<<a.height;
			}
		}
		return decode(a.code);
	}
	Val prevvalue(int s,int e,Val x,Val y)const{
		int lb = encode(x);
		int ub = encode(y)-1;
		Node a(-1,-1,-1,-1);
		for(int i=BITLEN-1;i>=0;i--){
			int ssum = bv[i].rank(s);
			int esum = bv[i].rank(e);
			int num1 = esum-ssum;
			int num0 = e-s-num1;
			if(ub&1<<i){
				if(num0){
					a = Node(i-1,s-ssum,e-esum,ub&~((1<<i)-1)&~(1<<i));
				}
				s = len-bv[i].rank(len) + ssum;
				e = s + esum-ssum;
			}else{
				s = s-ssum;
				e = e-esum;
			}
			if(s==e)break;
			if(i==0)return decode(ub);
		}
		if(a.code==-1)return NIL;
		for(;a.height>=0;a.height--){
			int ssum = bv[a.height].rank(a.s);
			int esum = bv[a.height].rank(a.e);
			int num1 = esum-ssum;
			int num0 = a.e-a.s-num1;
			int s0 = a.s-ssum;
			int s1 = len-bv[a.height].rank(len) + ssum;
			if(num1){
				a.s=s1;
				a.e=s1+num1;
				a.code|=1<<a.height;
			}else{
				a.s=s0;
				a.e=s0+num0;
			}
		}
		return decode(a.code);
	}
};


int main(){
	int n;
	vector<int> v;
	cin>>n;
	rep(i,n){
		int a;
		cin>>a;
		v.push_back(a);
	}
	WaveletMatrix wm(v);
	int q;
	cin>>q;
	rep(i,q){
		int l,r,d,a;
		int ans=INF;
		cin>>l>>r>>d;
		if(wm.rank(l,r+1,d)){
			ans=0;
		}else{
			a=wm.nextvalue(l,r+1,d,1<<20);
			if(a!=-1)ans=a-d;
			a=wm.prevvalue(l,r+1,0,d);
			if(a!=-1&&d-a<ans)ans=d-a;
		}
		cout<<ans<<endl;
	}
	return 0;
}