Artem 正在度假,想给他的两个队友买纪念品。沿街有n家纪念品商店。在第 i 家商店,Artem 可以用 ai 美元购买一件纪念品,并且他不能在一家商店购买多于一件纪念品。他不想让自己的团队产生嫉妒,所以他想买两件价格相差最小的纪念品。
Artsem 已访问购物街 m 次。由于某种奇怪的原因,第 i 天只有编号为 li 到 ri 的商店在营业(很奇怪?是的,但是您是否尝试过为范围查询问题想出一个合理的图例?)。每次访问时,Artem 都想知道他可以在开设的商店中购买的两种不同纪念品的最小可能价格差异。
换句话说,对于 Artem 的每次访问,您应该找到 |as - at| 的最小可能值其中 li ≤ s,t ≤ ri,s ≠ t。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105)。
第二行包含 n 个空格分隔的整数 a1, ..., an (0 ≤ ai ≤ 109)。
第三行包含查询数 m (1 ≤ m ≤ 3·105)。
接下来的 m 行描述查询。其中第 i 行包含两个空格分隔的整数 li 和 ri ,表示第 i 天营业的商店范围 (1 ≤ li < ri ≤ n)。
输出
在单独的行中打印每个查询的答案。
示例
输入 #1
8 3 1 4 1 5 9 2 6 4 1 8 1 3 4 8 5 7
输出 #1
0 1 1 3