Problem I: Hard Beans

Problem

大津大学では豆が盛んです。 N個の豆が一直線上に並んでいます。 それぞれ0から順にN−1まで番号がふられており、i番目の豆の硬さをa_iとします。

シアン君は理想の豆の硬さをDだと考えています。しかし、シアン君は面倒くさがりなのであまり遠くにある豆を取りに行きたくありません。したがって、シアン君はl番目の豆からr番目の豆の中で硬さがDに最も近い豆を知りたいと思っています。

シアン君はQ個の質問をしてくるので、それぞれの質問に対し閉区間[l,r]番目にある　| 豆の硬さ − D |　の最小値を求めるプログラムを作成してください。(ただし、| a | は aの絶対値を表します。)

Input

入力は以下の形式で与えられる。

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

1行目に、1つの整数Nが与えられる。2行目に、Nつの整数が空白区切りで与えられる。3行目に、クエリの数が１つの整数Qとして与えられる。続く4行から3+Q行までにクエリの値l,r,Dが与えられる。

Constraints

入力は以下の制約を満たす。

• 1 ≤ N ≤ 10⁵
• 0 ≤ |a_i| ≤ 10⁶ (0 ≤ i ≤ N−1)
• 1 ≤ Q ≤ 10⁵
• 0 ≤ D_i ≤ 10⁶
• 0 ≤ l_i ≤ r_i ≤ N−1

Output

各クエリに対し、Dと[l,r]番目の豆の中で硬さDに最も近い豆の硬さとの差の絶対値を1行に出力せよ。

Sample Input1

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

Sample Output1

0
1
1

Sample Input2

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

Sample Output2

1
0
1
90
1

---