题目描述

参考：Codeforces 765F

给出序列 $\{a_n\}$
给出 $m$ 个询问 $[L_i,R_i]$：询问 $\min\{|a_s-a_t|\}$，其中 $s, t\in [L_i,R_i], s \neq t$。

输入格式

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

输出格式

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

样例

输入

4
2 2 3 4
2
1 2
2 4

输出

0
1

数据范围与提示

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