题目描述

参考：Codeforces 765F

给出序列 ${a_n}$
给出 $m$ 个询问 $[L_i,R_i]$ : 询问 $min{|a_s-a_t|}, s, t\in [L_i,R_i],s \not = t$

输入格式

第一行一个整数 $ n $。
第二行 $ n $ 个整数，表示 $ a_i $。
第三行一个整数 $m$，表示询问个数。
之后的 $m$ 行，每行两个正整数，表示 $L_i, R_i$。

输出格式

共 $m$ 行，表示询问的答案。
特别的，如果不存在答案，输出 $2147483647$。

样例

input

4
2 2 3 4
2
1 2
2 4

output

0
1

数据范围与提示

$1\le n\le 10^5,1\le a_i \le 10^9,1\le m \le 3\times 10^5$