CF765F Souvenirs

Artsem 正在度假，想给两位队友买纪念品。街道上一共有 $n$ 家纪念品商店。在第 $i$ 家店里，Artsem 可以花 $a_i$ 美元购买一件纪念品，但每家店最多只能买一件。 为了避免队友互相嫉妒，他希望购买的两件纪念品价格尽可能接近。 Artsem 总共逛了这条街 $m$ 次。但在第 $i$ 天时，只有第 $l_i$ 到第 $r_i$ 家店铺开门（听起来很离谱对吧？但为了设计区间查询题目的背景设定也只能这样了）。 对于每次逛街，Artsem 都想知道在当天开门的店铺中，能买到的两件不同纪念品的最小价格差。 换句话说，对于 Artsem 的每次逛街，你需要找出满足 $l_i\le s, t \le r_i,s \ne t$ 时，$|a_s - a_t|$ 的最小可能值。

第一行，一个整数 $n\;(2\le n\le 10^5)$。 第二行，$n$ 个整数 $a_1,\cdots, a_n\;(0 \le  a_i \le 10^9)$。 第三行是，一个整数 $m\;(1 \le m \le  3\times 10^5)$，表示查询次数。 接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示第$i$ 天营业的店铺范围 $(1\le l_i

对每个查询输出一行，表示答案。